Interpolants in Nonlinear Theories Over the Reals

Sicun Gao, Damien ZuffereyTACAS 2016 · OpenReview

Abstract

We develop algorithms for computing Craig interpolants for first-order formulas over real numbers with a wide range of nonlinear functions, including transcendental functions and differential equations. We transform proof traces from $$\delta $$ -complete decision procedures into interpolants that consist of Boolean combinations of linear constraints. The algorithms are guaranteed to find the interpolants between two formulas A and B whenever $$A \wedge B$$ is not $$\delta $$ -satisfiable. At the same time, by exploiting $$\delta $$ -perturbations one can parameterize the algorithm to find interpolants with different positions between A and B. We show applications of the methods in control and robotic design, and hybrid system verification.
BibTeX
@inproceedings{gao2016interpolants,
  author = {Sicun Gao and Damien Zufferey},
  title = {{Interpolants in Nonlinear Theories Over the Reals}},
  booktitle = {TACAS},
  year = {2016},
  url = {https://openreview.net/forum?id=r5Hvtdc8lf},
}

Loading related content...

Figure