Nonlinear Craig interpolant generation

DOI10.1007/978-3-030-53288-8_20MaRDI QIDQ2225119zbMATH OpenOpenAlexFDO

Authors Ting Gan, Bican Xia, Bai Xue, Naijun Zhan, Liyun Dai

Publication date 4 February 2021

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1903.01297

zbMATH Keywords

Archimedean conditionCraig interpolantprogram verificationsemidefinite programmingsum of squares

Mathematics Subject Classification ID

Logic in computer science (03B70) Interpolation, preservation, definability (03C40) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Specification and verification (program logics, model checking, etc.) (68Q60) Semidefinite programming (90C22)

Abstract: Interpolation-based techniques have become popularized in recent years because of their inherently modular and local reasoning, which can scale up existing formal verification techniques like theorem proving, model-checking, abstraction interpretation, and so on, while the scalability is the bottleneck of these techniques. Craig interpolant generation plays a central role in interpolation-based techniques, and therefore has drawn increasing attentions. In the literature, there are various works done on how to automatically synthesize interpolants for decidable fragments of first-order logic, linear arithmetic, array logic, equality logic with uninterpreted functions (EUF), etc., and their combinations. But Craig interpolant generation for non-linear theory and its combination with the aforementioned theories are still in infancy, although some attempts have been done. In this paper, we first prove that a polynomial interpolant of the form $h(mathbfx)>0$ exists for two mutually contradictory polynomial formulas $phi(mathbfx,mathbfy)$ and $psi(mathbfx,mathbfz)$, with the form $f_{1}ge0wedgecdotswedge{f}_{n}ge0$, where $f_i$ are polynomials in $mathbfx,mathbfy$ or $mathbfx,mathbfz$, and the quadratic module generated by $f_i$ is Archimedean. Then, we show that synthesizing such interpolant can be reduced to solving a semi-definite programming problem ($mSDP$). In addition, we propose a verification approach to assure the validity of the synthesized interpolant and consequently avoid the unsoundness caused by numerical error in $mSDP$ solving. Finally, we discuss how to generalize our approach to general semi-algebraic formulas.

Recommendations

• Generating non-linear interpolants by semidefinite programming
• Craig interpolation in the presence of non-linear constraints
• Interpolants in nonlinear theories over the reals
• Sharper and Simpler Nonlinear Interpolants for Program Verification
• Constraint Solving for Interpolation

Cited in

(10)

• Encoding inductive invariants as barrier certificates: synthesis via difference-of-convex programming
• Probably approximately correct interpolants generation
• Interpolants in nonlinear theories over the reals
• NIL: learning nonlinear interpolants
• Interpolant synthesis for quadratic polynomial inequalities and combination with EUF
• Generating non-linear interpolants by semidefinite programming
• Craig interpolation in the presence of non-linear constraints
• Sharper and Simpler Nonlinear Interpolants for Program Verification
• Affine Loop Invariant Generation via Matrix Algebra
• Interpolation and model checking for nonlinear arithmetic

This page was built for publication: Nonlinear Craig interpolant generation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225119)