In mathematics and theoretical computer science, a semilinear set (also written semi-linear set) is a set of vectors of natural numbers or integers that can be built from finitely many linear sets, each generated by a base vector together with finitely many period vectors. Semilinear sets are a higher-dimensional analogue of an arithmetic progression: where a progression is generated by repeatedly adding one common difference, a linear set is generated by repeatedly adding any of several period vectors, in any combination and any number of times. Their importance rests on a series of equivalences established in the 1960s. The semilinear sets are exactly the sets definable in Presburger arithmetic, exactly the rational subsets of the commutative monoid N d {\displaystyle \mathbb {N} ^{d}} , and exactly the sets arising as commutative images of context-free languages. They therefore serve as a finite, effective representation of certain infinite sets of integer vectors, and are used throughout formal language theory, verification and related areas.
Definition A subset L ⊆ N d {\displaystyle L\subseteq \mathbb {N} ^{d}} is linear if it is of the form
L = { b + ∑ i = 1 m k i p i : k 1 , … , k m ∈ N } , {\displaystyle L=\left\{\mathbf {b} +\sum _{i=1}^{m}k_{i}\mathbf {p} _{i}\,\colon \,k_{1},\dots ,k_{m}\in \mathbb {N} \right\},}
where m ∈ N {\displaystyle m\in \mathbb {N} } and b , p 1 , … , p m {\displaystyle \mathbf {b} ,\mathbf {p} _{1},\dots ,\mathbf {p} _{m}} are fixed vectors in N d {\displaystyle \mathbb {N} ^{d}} , called the base vector and the period vectors respectively. A subset of N d {\displaystyle \mathbb {N} ^{d}} is semilinear if it is a finite union of linear sets. The number m {\displaystyle m} of periods may be zero, so that every singleton is linear; the empty set is semilinear as the empty union. A pair consisting of a base vector and a finite set of period vectors is called a representation of the linear set it generates, and a finite collection of such pairs a representation of the semilinear set they generate; representations are not unique. A linear set with a single period vector p {\displaystyle \mathbf {p} } is the set of terms of the arithmetic progression b , b + p , b + 2 p , … {\displaystyle \mathbf {b} ,\mathbf {b} +\mathbf {p} ,\mathbf {b} +2\mathbf {p} ,\ldots } , and a general linear set is generated in the same way but from several common differences at once, applied in any combination and any number of times. The coefficients k i {\displaystyle k_{i}} are unbounded, which distinguishes a linear set from a finite generalized arithmetic progression, where each coefficient is restricted to a bounded range.
Variants The same definition is used for subsets of Z d {\displaystyle \mathbb {Z} ^{d}} , where the base and period vectors are allowed to have negative entries, while the coefficients k i {\displaystyle k_{i}} still range over N {\displaystyle \mathbb {N} } ; in that setting the semilinear sets are the rational subsets of the group ( Z d , + ) {\displaystyle (\mathbb {Z} ^{d},+)} . More generally, the definition makes sense in any finitely generated commutative monoid: a subset is linear if it has the form x + B ⊕ {\displaystyle x+B^{\oplus }} , where x {\displaystyle x} is an element of the monoid and B ⊕ {\displaystyle B^{\oplus }} is the submonoid generated by a finite set B {\displaystyle B} , and semilinear if it is a finite union of such sets. Because of the equivalence with definability in Presburger arithmetic, semilinear sets are also called Presburger sets or Presburger-definable sets.
… excerpt ends here. Continue reading the full article.
