Detail

Vijay D’Silva, Daniel Kroening, Mitra Purandare, Georg Weissenbacher

Technical Report 652
ETH Zürich
Computer Systems Institute
11/2009.

Keywords: interpolation, verification

Pages: 30
Language: EN

Interpolant Strength

Interpolant-based model checking is an approximate method for computing invariants of transition systems.

The performance of the model checker is contingent on the approximation computed, which in turn depends on the logical strength of the interpolants.  A good approximation is coarse enough to enable rapid convergence but strong enough to be contained within the weakest inductive invariant.

We present a system for constructing propositional interpolants of different strength from a resolution refutation. This system subsumes existing methods and allows interpolation systems to be ordered by the logical strength of the obtained interpolants.

Interpolants of different strength can also be obtained by transforming a resolution proof. We analyse an existing proof transformation, generalise it, and characterise the interpolants obtained.