A linear set is any set of the form a + span (b1,..., bk). Here the plus sign means set addition:

X + Y = {a + b: a in X and b in Y}. The span of a set S is the set of all elements that can be made

by adding together a finite sequence of elements from S.

A semilinear set is the union of finitely many linear sets.

A linear set is simple if the vectors b1,..., bk are linearly independent as vectors of real numbers.

A set is semisimple if it is the union of finitely many simple sets.

We proved on 15 February 2013 in H401 class that a subset of N is semilinear iff it is semisimple iff

the corresponding subset of a* is the language of some DFA.

In fact the semilinear and semisimple subsets of N^d are the same for any d. [NEED A PROOF]

-- BarrinG - 2013-02-07

This topic: H401 > WebHome > SemilinearSets
Topic revision: r2 - 2013-02-15 - BarrinG

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback