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

Topic revision: r2 - 2013-02-15 - BarrinG
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 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

mersin escort adana escort izmir escort gaziantep escort