TL;DR
This paper introduces a novel "sup-inf" method for automatically proving the validity of a specific class of formulas in Presburger Arithmetic, namely those with only universally quantified variables. This approach offers an efficient alternative to existing methods, particularly for verification conditions arising from program validation, by avoiding exhaustive searches and facilitating "proof by cases."
What Problem Does This Paper Address?
Presburger Arithmetic is a formal system for reasoning about integers, allowing for addition, subtraction, integer constants, inequalities, and quantification. A key challenge in using Presburger Arithmetic for program verification is the automatic determination of the truth or falsity of complex formulas derived from program properties. While decision procedures exist, some methods, like Cooper's, can require extensive searches through consecutive integers, especially when dealing with non-unity coefficients in inequalities. This paper tackles the problem of efficiently proving formulas with universally quantified variables, a common occurrence in program verification, by developing a more streamlined and less computationally intensive approach.
Methods
The paper proposes a "sup-inf" method for proving the validity of universally quantified Presburger formulas. The core idea is to negate the formula and transform it into a disjunctive normal form. Each disjunct is then converted into a set of inequalities involving the variables. The method then focuses on determining the "supremum" (least upper bound) and "infimum" (greatest lower bound) of these variables within the constraints imposed by the inequalities.
The key algorithms are SUP and INF, which compute these bounds. These algorithms are designed to handle "quasi-linear" formulas, an extension of Presburger formulas that allows rational numbers as constants and includes max and min operations. The validity of the original formula is established if, for at least one variable, the interval defined by its infimum and supremum contains no integers. This avoids the need for enumerating integer values. The paper also introduces SUPP and INFF to handle cases where the bounds themselves depend on the variable being bounded.
Datasets
Not discussed in the paper. The paper focuses on a general algorithmic method and illustrates its application with examples derived from program verification scenarios, rather than specific datasets.
Key Insights and Ideas
- "Sup-Inf" as a Generalization: The sup-inf method provides a unified framework for determining the validity of universally quantified Presburger formulas by focusing on the bounds of variables.
- Efficiency over Enumeration: The method avoids the potentially exponential cost of enumerating integer values, which is a significant advantage for automated theorem proving.
- Handling "Proof by Cases": The sup-inf method is particularly well-suited for scenarios requiring "proof by cases," as the derived inequalities can be stored and reused for different sub-goals.
- Quasi-Linear Formulas: The extension to quasi-linear formulas, allowing rational constants and
max/minoperations, broadens the applicability of the method to a wider range of program verification problems. - Concise Representation of Hypotheses: The method allows for the concise storage of complex hypotheses (sets of inequalities), which can then be efficiently used to prove various conclusions.
Key Results
The paper presents algorithms (SUP, INF, SUPP, INFF) for computing the bounds of variables within a set of quasi-linear inequalities. It demonstrates how these algorithms can be used to determine the validity of universally quantified Presburger formulas. While specific quantitative results (e.g., speedup percentages) are not detailed, the paper emphasizes the method's efficiency and its successful implementation within an automatic theorem proving system. Several examples are provided to illustrate the procedure, including the conversion of a complex theorem into a manageable set of inequalities and the subsequent application of the sup-inf method.
Limitations and Future Work
The authors acknowledge that their method, as described, handles only universally quantified variables and it is "not clear whether our methods can be extended to handle all Presburger formulas, with both universal and existential quantification." They also note that while their method is generally efficient, the "sup-inf" procedure can be viewed as another method for solving integer programming problems, suggesting a connection to existing optimization techniques. The paper hints at further details and proofs in a companion memo (ATP 18), indicating that the current paper focuses on the method's description and application.
Summary updated