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

Ideas, requests, problems regarding UMass CS EdLab? Send feedback