Abstract

Generalizing Cooper’s method of quantifier elimination for Presburger arithmetic, we give a new proof that all parametric Presburger families \ [as defined by Woods ] are definable by formulas with polynomially bounded quantifiers in an expanded language with predicates for divisibility by f for every polynomial \. In fact, this quantifier bounding method works more generally in expansions of Presburger arithmetic by multiplication by scalars \: \alpha \in R, t \in X\}\) where R is any ring of functions from X into \.