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

Edit | Attach | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions

Copyright © 2008-2018 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