Efficient generation of Craig interpolants in satisfiability modulo theories

DOI10.1145/1838552.1838559zbMATH Open1351.68247arXiv0906.4492OpenAlexW2003690673WikidataQ62041234 ScholiaQ62041234MaRDI QIDQ2946624FDOQ2946624

Authors: Alessandro Cimatti, Alberto Griggio, Roberto Sebastiani 

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Abstract: The problem of computing Craig Interpolants has recently received a lot of interest. In this paper, we address the problem of efficient generation of interpolants for some important fragments of first order logic, which are amenable for effective decision procedures, called Satisfiability Modulo Theory solvers. We make the following contributions. First, we provide interpolation procedures for several basic theories of interest: the theories of linear arithmetic over the rationals, difference logic over rationals and integers, and UTVPI over rationals and integers. Second, we define a novel approach to interpolate combinations of theories, that applies to the Delayed Theory Combination approach. Efficiency is ensured by the fact that the proposed interpolation algorithms extend state of the art algorithms for Satisfiability Modulo Theories. Our experimental evaluation shows that the MathSAT SMT solver can produce interpolants with minor overhead in search, and much more efficiently than other competitor solvers.

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

Recommendations

• Efficient Interpolant Generation in Satisfiability Modulo Theories
• Efficient Interpolant Generation in Satisfiability Modulo Linear Integer Arithmetic
• Efficient interpolant generation in satisfiability modulo linear integer arithmetic
• Interpolant Generation for UTVPI
• Ground Interpolation for Combined Theories

zbMATH Keywords

SMTCraig interpolationdecision procedures

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Interpolation, preservation, definability (03C40)

Cited In (26)

• \textsc{OptiMathSAT}: a tool for optimization modulo theories
• Optimization modulo theories with linear rational costs
• Whale: an interpolation-based algorithm for inter-procedural verification
• Local abstraction refinement for probabilistic timed programs
• Farkas-based tree interpolation
• Interpolant Generation for UTVPI
• Ground Interpolation for Combined Theories
• Labelled interpolation systems for hyper-resolution, clausal, and local proofs
• Interpolation systems for ground proofs in automated deduction: a survey
• Craig interpolation in the presence of non-linear constraints
• Parallelizing SMT solving: lazy decomposition and conciliation
• Automated Deduction – CADE-20
• Efficient Interpolant Generation in Satisfiability Modulo Theories
• Efficient Interpolant Generation in Satisfiability Modulo Linear Integer Arithmetic
• On recursion-free Horn clauses and Craig interpolation
• Efficient interpolant generation in satisfiability modulo linear integer arithmetic
• Verification Modulo theories
• A combination of rewriting and constraint solving for the quantifier-free interpolation of arrays with integer difference constraints
• Proof tree preserving interpolation
• Satisfiability modulo theories
• Invariant checking for SMT-based systems with quantifiers
• Generalized Craig interpolation for stochastic satisfiability modulo theory problems
• On interpolation in automated theorem proving
• Infinite-state invariant checking with IC3 and predicate abstraction
• Efficient Generation of Small Interpolants in CNF
• Transition power abstractions for deep counterexample detection

This page was built for publication: Efficient generation of Craig interpolants in satisfiability modulo theories

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