Weak quantifier elimination for the full linear theory of the integers

We describe a weak quantifier elimination procedure for the full linear theory of the integers. This theory is a generalization of Presburger arithmetic, where the coefficients are arbitrary polynomials in non-quantified variables. The notion of weak quantifier elimination refers to the fact that the result possibly contains bounded quantifiers. For fixed choices of parameters these bounded quantifiers can be expanded into disjunctions or conjunctions. We furthermore give a corresponding extended quantifier elimination procedure, which delivers besides quantifier-free equivalents also sample values for quantified variables. Our methods are efficiently implemented within the computer logic system REDLOG, which is part of REDUCE. Various examples demonstrate the applicability of our methods. These examples include problems currently discussed in practical computer science.