
> 
> **Q1.** What are the "standard" techniques (if any) used to prove that a set of vectors in $\mathbb{N}^k$ defined using a set of constraints among the components is (or is not) a semilinear set (i.e. a finite union of linear sets) ?
> 
> 
> 


For example, given:


$A = \{ \langle x\_1, x\_2, x\_3, x\_4, x\_5, x\_6 \rangle \mid \sum\_i x\_i \equiv 0 \bmod 6 \land [x\_1 + x\_2 + x\_3 \neq x\_4+x\_5+x\_6] \land [(x\_1 + x\_2 \neq x\_3 + x\_4) \lor (x\_3 + x\_4 \neq x\_5 + x\_6) ]\} $


how can I (dis)prove that $A$ is semilinear?



> 
> **Q2.** Can this process be automated assuming that the conditions are given using a set of logic expressions with numeric constants and operators $\land, \lor, +, -, =, \neq, \leq$? And if it can be automated, what is its (computational) complexity?
> 
> 
> 



Techniques to (dis)prove that a set is semilinear
These are the definable sets in Presburger arithmetic <https://en.m.wikipedia.org/wiki/Presburger_arithmetic>. They are also the commutative images of context free languages. 


