Semilinear set

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 $\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\subseteq \mathbb {N} ^{d}$ is linear if it is of the form $$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\in \mathbb {N}$ and $\mathbf {b} ,\mathbf {p} _{1},\dots ,\mathbf {p} _{m}$ are fixed vectors in $\mathbb {N} ^{d}$, called the base vector and the period vectors respectively. A subset of $\mathbb {N} ^{d}$ is semilinear if it is a finite union of linear sets.

The number $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 $\mathbf {p}$ is the set of terms of the arithmetic progression $\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}$ 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 $\mathbb {Z} ^{d}$, where the base and period vectors are allowed to have negative entries, while the coefficients $k_{i}$ still range over $\mathbb {N}$; in that setting the semilinear sets are the rational subsets of the group $(\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^{\oplus }$, where $x$ is an element of the monoid and $B^{\oplus }$ is the submonoid generated by a finite set $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.

Examples

• Every finite subset of $\mathbb {N} ^{d}$ is semilinear: it is the union of one linear set per element, each with that element as base and no period vectors.
• The set of even natural numbers is the linear set with base $0$ and single period $2$, and more generally each arithmetic progression $\{b+kp\mid k\in \mathbb {N} \}$ is the linear set with base $b$ and single period $p$.
• A linear set need not be an arithmetic progression. The linear set with base $0$ and periods $3$ and $5$ is the numerical semigroup $\{3a+5b\mid a,b\in \mathbb {N} \}=\{0,3,5,6,8,9,10,\ldots \}$, which omits $1,2,4$ and $7$; the largest omitted value is the Frobenius number $3\cdot 5-3-5=7$. The same set also has a representation as a union of five linear sets, namely the singletons $\{0\},\{3\},\{5\},\{6\}$ together with the set of base $8$ and period $1$, which illustrates that representations are not unique.
• In $\mathbb {N} ^{2}$, the set $\{(x,y)\mid x=y\}$ is linear, with base $(0,0)$ and period $(1,1)$; so is $\{(x,y)\mid x\leq y\}$, with base $(0,0)$ and periods $(1,1)$ and $(0,1)$, its elements being the vectors $(a,a+b)$ for $a,b\in \mathbb {N}$.
• The union of the two coordinate axes of $\mathbb {N} ^{2}$ is semilinear, being the union of the linear set with base $(0,0)$ and period $(1,0)$ and the linear set with base $(0,0)$ and period $(0,1)$. It is not itself linear: a linear set containing $(1,0)$ and $(0,1)$ has base $(0,0)$ and both vectors among its periods, and therefore also contains $(1,1)$.
• The set of powers of two is not semilinear, since the semilinear subsets of $\mathbb {N}$ are exactly the ultimately periodic sets. For the same reason the set of primes and the set of squares are not semilinear.
• The integer points of a rational cone form a monoid generated by an integral Hilbert basis, which may properly contain the extreme rays. The set $\{(x,y)\mid y\leq x\leq 3y\}$ of integer points of the cone generated by $(1,1)$ and $(3,1)$ is linear, with base $(0,0)$ and periods $(1,1)$, $(2,1)$ and $(3,1)$. The two generators alone do not suffice, since $(2,1)$ lies in the cone but is not a non-negative integer combination of them. With all three periods, the elements with second coordinate $k$ are exactly the pairs $(x,k)$ with $k\leq x\leq 3k$, because the sums of $k$ values drawn from $\{1,2,3\}$ are precisely the integers from $k$ to $3k$. Each row of the set is therefore an unbroken interval, three points wider at every step, and the rows continue upwards without bound:

 y
 ⋮
 4 │         ● ● ● ● ● ● ● ● ●
 3 │       ● ● ● ● ● ● ●
 2 │     ● ● ● ● ●
 1 │   ● ● ●
 0 │ ●
   └─────────────────────────────
     0 1 2 3 4 5 6 7 8 9  ...   x

Equivalent characterisations

Presburger arithmetic

Seymour Ginsburg and Edwin Spanier proved that the semilinear sets coincide with the sets defined by Presburger formulas, so that every such set has both an "internal" description as a finite union of linear sets and an "external" description by a formula of Presburger arithmetic, each effectively obtainable from the other.

Rational sets

Samuel Eilenberg and Marcel-Paul Schützenberger showed that the semilinear sets are precisely the rational subsets of the commutative monoid $\mathbb {N} ^{d}$, that is, the sets obtainable from finite sets by union, elementwise addition and iteration.

Parikh images

The Parikh image of a word over an alphabet of $d$ letters is the vector in $\mathbb {N} ^{d}$ recording how many times each letter occurs; the Parikh image of a language is the set of images of its words. Parikh's theorem states that the Parikh image of every context-free language is semilinear; conversely every semilinear set is the Parikh image of a regular language, so that every context-free language has the same Parikh image as some regular language.

Solutions of linear systems

The set of solutions in $\mathbb {N} ^{d}$ of a finite system of linear equalities and inequalities with integer coefficients is semilinear, since such a system is expressible as a quantifier-free Presburger formula; the same holds for finite unions of such solution sets.

Closure properties

The equivalence with Presburger arithmetic gives closure under the Boolean operations of union, intersection and complement, and under projection, since the corresponding operations on formulas are disjunction, conjunction, negation and existential quantification. Closure under intersection and complement is not apparent from the definition: the intersection of two linear sets need not be linear, and the complement of a linear set need not be. Eilenberg and Schützenberger derived the same closure properties algebraically, showing that the rational subsets of a finitely generated commutative monoid form a Boolean algebra.

Semilinear sets are also closed under elementwise addition and under iteration, both immediately from the description as rational sets, and under images and preimages of affine maps with integer coefficients.

Algorithmic properties

Presburger arithmetic is decidable, a result of Mojżesz Presburger. Since a semilinear representation and a defining Presburger formula can each be computed from the other, membership, emptiness, inclusion and equivalence questions for semilinear sets can be phrased as Presburger sentences and settled by the decision procedure, in either presentation.

These procedures are expensive in general: deciding the truth of a Presburger sentence requires doubly exponential nondeterministic time in the worst case. Satisfiability for the existential fragment, which suffices to express membership in a semilinear set given by a representation with binary-encoded vectors, is NP-complete.

Descriptional complexity

Semilinear sets are usually presented implicitly, by a Presburger formula or by other means rather than by an explicit list of base and period vectors, and the effect of Boolean operations on the size of a description had chiefly been studied for the explicit presentation. Dmitry Chistikov and Christoph Haase developed a framework for implicitly presented semilinear sets in which size is measured by the norm, the largest magnitude of a generator, and assembled a collection of operations and decompositions with bounds stated in those terms; their approach yields exponentially better bounds for complement and for set difference than were previously known.

Bounds on the magnitude of minimal solutions to systems of linear integer equalities and inequalities, due to Joachim von zur Gathen and Malte Sieveking, underlie many such estimates.

Applications

Semilinearity is a recurring dividing line in the analysis of infinite-state systems, because a semilinear set of configurations can be manipulated symbolically and tested by the decision procedures for Presburger arithmetic. Oscar Ibarra showed that the reachability sets of reversal-bounded multicounter machines are effectively semilinear, which yields decidability of a range of verification questions for them. By contrast, John Hopcroft and Jean-Jacques Pansiot showed that reachability sets of vector addition systems are effectively semilinear in dimension at most five but not in general, exhibiting a six-dimensional system whose reachability set is not semilinear.

History

The notion arose from work on formal language theory in the 1960s. Ginsburg and Spanier introduced bounded ALGOL-like languages in 1964, where linear and semilinear sets appear in the analysis of their structure, and established the equivalence with Presburger arithmetic in 1966. Rohit Parikh proved the semilinearity of the commutative images of context-free languages in a 1961 technical report, published in revised form in 1966, and Eilenberg and Schützenberger gave the characterisation in terms of rational sets in 1969.

See also

• Presburger arithmetic
• Parikh's theorem
• Generalized arithmetic progression
• Rational set
• Context-free language
• Numerical semigroup

References

• Chistikov, Dmitry; Haase, Christoph (2016). "The Taming of the Semi-Linear Set". 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs). Vol. 55. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 128:1–128:13. doi:10.4230/LIPIcs.ICALP.2016.128. ISBN 978-3-95977-013-2.
• Eilenberg, Samuel; Schützenberger, Marcel-Paul (1969). "Rational sets in commutative monoids". Journal of Algebra. 13 (2): 173–191. doi:10.1016/0021-8693(69)90070-2.
• Ginsburg, Seymour; Spanier, Edwin Henry (1964). "Bounded ALGOL-like languages". Transactions of the American Mathematical Society. 113 (2): 333–368. doi:10.1090/S0002-9947-1964-0181500-1. MR 0181500.
• Ginsburg, Seymour; Spanier, Edwin Henry (1966). "Semigroups, Presburger formulas, and languages" (PDF). Pacific Journal of Mathematics. 16 (2): 285–296. doi:10.2140/pjm.1966.16.285. MR 0191770.
• Haase, Christoph (2018). "A survival guide to Presburger arithmetic" (PDF). ACM SIGLOG News. 5 (3): 67–82. doi:10.1145/3242953.3242964. S2CID 51847374.
• Hopcroft, John; Pansiot, Jean-Jacques (1979). "On the reachability problem for 5-dimensional vector addition systems". Theoretical Computer Science. 8 (2): 135–159. doi:10.1016/0304-3975(79)90041-0.
• Ibarra, Oscar H. (1978). "Reversal-bounded multicounter machines and their decision problems". Journal of the ACM. 25 (1): 116–133. doi:10.1145/322047.322058.
• Parikh, R. J. (15 January 1961). "Language-Generating Devices". Quarterly Progress Report (60). Cambridge, Massachusetts: Research Laboratory of Electronics, Massachusetts Institute of Technology: 199–212.
• Parikh, R. J. (1966). "On Context-Free Languages". Journal of the ACM. 13 (4): 570–581. doi:10.1145/321356.321364. S2CID 12263468.
• Presburger, Mojżesz (1929). "Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt". Comptes Rendus du I Congrès de Mathématiciens des Pays Slaves (in German). pp. 92–101.
• Ramírez Alfonsín, Jorge L. (2005). The Diophantine Frobenius Problem. Oxford Lecture Series in Mathematics and its Applications. Vol. 30. Oxford University Press. ISBN 978-0-19-856820-9.
• Sakarovitch, Jacques (2009) [French original, Vuibert, 2003]. Elements of Automata Theory. Translated by Thomas, Reuben. Cambridge University Press. ISBN 978-0-521-84425-3.
• Schrijver, Alexander (1986). Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Chichester: John Wiley & Sons. ISBN 978-0-471-90854-8. LCCN 85012314. MR 0874114. OCLC 12215661.
• von zur Gathen, Joachim; Sieveking, Malte (1978). "A bound on solutions of linear integer equalities and inequalities". Proceedings of the American Mathematical Society. 72 (1): 155–158. doi:10.1090/S0002-9939-1978-0500555-0.

External links

• Thomas Kern — Regular Languages and Model Theory 23: Semilinear Sets on YouTube