Proving that a set is/is not semilinear

Question

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?

Answer 1

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.

Answer 2

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.