Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse




Journal Article

Constraint Solving for Interpolation


Rybalchenko,  Andrey
Automation of Logic, MPI for Informatics, Max Planck Society;

Sofronie-Stokkermans,  Viorica
Automation of Logic, 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. (2010). Constraint Solving for Interpolation. Journal of Symbolic Computation, 45(11), 1212-1233. doi:101016/j.jsc.2010.06.005.

Cite as:
Interpolation is an important component of recent methods for program verification. It provides a natural and effective means for computing the 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 a black-box fashion. We provide experimental evidence of the practical applicability of our algorithm.