file.pdf (2.03 MB)

Deciding quantifier-free Presburger formulas using finite instantiation based on parameterized solution bounds

Download (2.03 MB)
journal contribution
posted on 01.05.2001 by Sanjit A. Seshia, Randal Bryant
Abstract: "Given a formula [Phi] in quantifier-free Presburger arithmetic, it is well known that, if there is a satisfying solution to [Phi], there is one whose size, measured in bits, is polynomially bounded in the size of [Phi]. In this paper, we consider a special class of quantifier-free Presburger formulas in which most linear constraints are separation (difference-bound) constraints, and the non-separation constraints are sparse. This class has been observed to commonly occur in software verification problems. We derive a new solution bound in terms of parameters characterizing the sparseness of linear constraints and the number of non-separation constraints, in addition to traditional measures of formula size. In particular, the number of bits needed per integer variable is linear in the number of non-separation constraints and logarithmic in the number and size of non-zero coefficients in them, but is otherwise independent of the total number of linear constraints in the formula. The derived bound can be used in a decision procedure based on instantiating integer variables over a finite domain and translating the input quantifier-free Presburger formula to an equi-satisfiable Boolean formula, which is then checked using a Boolean satisfiability solver. We present empirical evidence indicating that this method can greatly outperform other decision procedures."


Publisher Statement

Appeared in the Proceedings of the First International Workshop on Mathematical Methods, Models and Architectures for Computer Network Security — MMM’01 (V.I. Gorodetski, V.A. Skormin and L.J. Popyack, editors), pp. 159–176, c Springer-Verlag LNCS 2052, St. Petersburg, Russia, 21–23 May 2001