English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Interpolation-based techniques have become popularized in recent yearsbecause of their inherently modular and local reasoning, which can scale upexisting formal verification techniques like theorem proving, model-checking,abstraction interpretation, and so on, while the scalability is the bottleneckof these techniques. Craig interpolant generation plays a central role ininterpolation-based techniques, and therefore has drawn increasing attentions.In the literature, there are various works done on how to automaticallysynthesize interpolants for decidable fragments of first-order logic, lineararithmetic, array logic, equality logic with uninterpreted functions (EUF),etc., and their combinations. But Craig interpolant generation for non-lineartheory and its combination with the aforementioned theories are still ininfancy, although some attempts have been done. In this paper, we first provethat a polynomial interpolant of the form $h(\mathbf{x})>0$ exists for twomutually contradictory polynomial formulas $\phi(\mathbf{x},\mathbf{y})$ and$\psi(\mathbf{x},\mathbf{z})$, with the form $f_1\ge0\wedge\cdots\wedgef_n\ge0$, where $f_i$ are polynomials in $\mathbf{x},\mathbf{y}$ or$\mathbf{x},\mathbf{z}$, and the quadratic module generated by $f_i$ isArchimedean. Then, we show that synthesizing such interpolant can be reduced tosolving a semi-definite programming problem (${\rm SDP}$). In addition, wepropose a verification approach to assure the validity of the synthesizedinterpolant and consequently avoid the unsoundness caused by numerical error in${\rm SDP}$ solving. Finally, we discuss how to generalize our approach togeneral semi-algebraic formulas.

Nonlinear Craig Interpolant Generation