Editing Presburger arithmetic (section)

==Applications==
Because Presburger arithmetic is decidable, [[automatic theorem prover]]s for Presburger arithmetic exist. For example, the [[Coq (software)|Coq]] and [[Lean (proof assistant)|Lean]] proof assistant systems feature the tactic ''omega'' for Presburger arithmetic and the [[Isabelle (proof assistant)|Isabelle proof assistant]] contains a verified quantifier elimination procedure by {{harvtxt|Nipkow|2010}}. The double exponential complexity of the theory makes it infeasible to use the theorem provers on complicated formulas, but this behavior occurs only in the presence of nested quantifiers: {{harvtxt|Nelson|Oppen|1978}} describe an automatic theorem prover that uses the [[simplex algorithm]] on an extended Presburger arithmetic without nested quantifiers to prove some of the instances of quantifier-free Presburger arithmetic formulas. More recent [[satisfiability modulo theories]] solvers use complete [[integer programming]] techniques to handle quantifier-free fragment of Presburger arithmetic theory.{{sfn|King|Barrett|Tinelli|2014}}

Presburger arithmetic can be extended to include multiplication by constants, since multiplication is repeated addition. Most array subscript calculations then fall within the region of decidable problems.<ref>For example, in the [[C (programming language)|C programming language]], if <code>a</code> is an array of 4 bytes element size, the expression <code>a[i]</code> can be translated to <code>a<sub>baseadr</sub>+i+i+i+i</code>, which fits the restrictions of Presburger arithmetic.</ref> This approach is the basis of at least five{{cn|date=October 2024}} proof-of-[[Correctness (computer science)|correctness]] systems for [[computer programs]], beginning with the [[Stanford Pascal Verifier]] in the late 1970s and continuing through to Microsoft's Spec# system of 2005.