SemiLinearSets

See the definition for linear and semilinear sets in the following: SemiLinearSets.pdf

The old tex file is attached here: SemiLinearSets.tex

Definition (Linear Set) Let $N$ be the set of nonnegative integers and $k$ be a positive integer. A set $$S\subseteq N^{{k} $i s a^{″} l i n e a r s e t^{″} i f$ \exists v_{0},v_{1},...,v_{t} $i n$ N}{k}$$ such that

$S = {v | v = v_{0} + a_{1} v_{1} + . . . + a_{t} v_{t}, a_{i} \in N}$ $

The vector $v_{0}$ (referred to as the constant vector) and $v_{1}, v_{2}, . . ., v_{t}$ (referred to as the periods) are called the generators of the linear set $S$ .

Definition (Semilinear Set) A set $$S\subseteq N^{{k} $i s^{″} s e m i l i n e a r^{″} i f i t i s a f i n i t e u n i o n o f l i n e a r s e t s .$ \emptyset $i s a t r i v i a l s e m i l i n e a r s e t w h e r e t h e s e t o f g e n e r a t o r s i s e m p t y .^{″} E v e r y f i n i t e s u b s e t o f^{″}$ N}{k}$$ is semilinear - it is a finite union of linear sets whose generators are constant vectors. Clearly, semilinear sets are closed under union and projection. It is also know that semilinear sets are closed under intersection and complementation.

The definition are from: [http://www.eecs.wsu.edu/~zdang/papers/catalytic.pdf Catalytic P Systems, Semilinear Sets, and Vector Addition Systems]