A Practical Decision Procedure for Arithmetic with Function Symbols
Robert E. Shostak · Journal of the ACM · 1979
A practical procedure is presented for an extension of quantifier-free Presburger arithmetic that permits arbitrary unmterpreted predicate and function symbols This theory includes many of the formulas one tends to encounter in program venficatlon and is powerful enough to encode the semantics of array operators as well as MAX, MIN, and ABSVALUE An implementation of the procedure has proved to be of great value in a program verlficauon system developed at SRI for the United States Air Force
Cited by 171 works. doi:10.1145/322123.322137 Open-access PDF
Authors
References
- Outline of an algorithm for integer solutions to linear programs
- Towards a Mathematical Science of Computation
- On the SUP-INF Method for Proving Presburger Formulas
- An algorithm for reasoning about equality
- A 222pn upper bound on the complexity of Presburger Arithmetic
- Verifying programs by algebraic and logical reduction
- A simplifier based on efficient decision algorithms
- An application of mathematical logic to the integer linear programming problem.