Complexity of subcases of Presburger arithmetic
Bruno Scarpellini · Transactions of the American Mathematical Society · 1984
We consider formula subclasses of Presburger arithmetic which have a simple structure in one sense or the other and investigate their computational complexity. We also prove some results on the lower bounds of lengths of formulas which are related to questions on quantifier elimination.