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

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.