A subset $X$ of $\mathbb{N}^n$ is linear if it is in the form:

$u_0 + \langle u_1,...,u_m \rangle = \{ u_0 + t_1 u_1 + ... + t_m u_m \mid t_1,...,t_n \in \mathbb{N}\}$ for some $u_0,...,u_m \in \mathbb{N}^n$

$X$ is semilinear if it is the union of finitely many linear subsets.

What are the techniques used to prove that a set is not semilinear (or is semilinear)?

For example I would like to know/prove if the following subset is not semilinear:

$X = \{ \langle x, y_1, y_2, z_1, z_2, w \rangle \}$ in which:

($x \geq y_1+y_2 +z_1+z_2+w$) OR
($w \geq x + y_1+y_2 +z_1+z_2$) OR
($x+y_1 = y_2+z_1 +z_2+w$ AND $x\neq y_2$ AND $y_1 \neq w$) OR
($x + y_1 + y_2 + z_1 = z_2 +w$ AND $x \neq z_2$ AND $z_1 \neq w$)

Any suggestions?


Semilinear sets are precisely the sets definable in Presburger arithmetic (i.e. the language of arithmetic with addition and less-than operators, but without multiplication). This is a theorem of Seymour Ginsburg and Edwin H. Spanier (1966).

Since you have defined the set in your question by a Presburger formula, it must be semilinear.


Semilinear sets form a Boolean algebra so you can use union, intersection and complement to simplify your life. They are also closed under projection. The commutative image of a context-free language is semilinear by Parikh's theorem. You can prove your set $X$ is semilinear using these facts.

For instance using a stack you can check if you have more $x$'s or $w$'s than the other variables combined so Parikh's theorem implies the first two parts of the definition of $X$ are semilinear. Closure under Boolean operations easily deals with the rest.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.