Subclasses of Presburger Arithmetic and the Weak EXP Hierarchy

Christoph Haase

It is shown that for any fixed $i>0$, the ${\Sigma }_{i+1}$-fragment of Presburger arithmetic, i.e., its restriction to $i+1$ quantifier alternations beginning with an existential quantifi…