Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse




Conference Paper

Constraint Solving for Interpolation


Rybalchenko,  Andrey
Programming Logics, MPI for Informatics, Max Planck Society;

Sofronie-Stokkermans,  Viorica
Automation of Logic, MPI for Informatics, Max Planck Society;
Programming Logics, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Rybalchenko, A., & Sofronie-Stokkermans, V. (2007). Constraint Solving for Interpolation. In B. Cook, & A. Podelski (Eds.), Verification, Model Checking and Abstract Interpretation: 8th International Conference, VMCAI 2007 (pp. 346-362). Berlin, Germany: Springer.

Cite as:
Interpolation is an important component of recent methods for program verification. It provides a natural and effective means for computing separation between the sets of `good' and `bad' states. The existing algorithms for interpolant generation are proof-based: They require explicit construction of proofs, from which interpolants can be computed. Construction of such proofs is a difficult task. We propose an algorithm for the generation of interpolants for the combined theory of linear arithmetic and uninterpreted function symbols that does not require a priori constructed proofs to derive interpolants. It uses a reduction of the problem to constraint solving in linear arithmetic, which allows application of existing highly optimized Linear Programming solvers in black-box fashion. We provide experimental evidence of the practical applicability of our algorithm.