Computing small unsatisfiable cores in satisfiability modulo theories
From MaRDI portal
Abstract: The problem of finding small unsatisfiable cores for SAT formulas has recently received a lot of interest, mostly for its applications in formal verification. However, propositional logic is often not expressive enough for representing many interesting verification problems, which can be more naturally addressed in the framework of Satisfiability Modulo Theories, SMT. Surprisingly, the problem of finding unsatisfiable cores in SMT has received very little attention in the literature. In this paper we present a novel approach to this problem, called the Lemma-Lifting approach. The main idea is to combine an SMT solver with an external propositional core extractor. The SMT solver produces the theory lemmas found during the search, dynamically lifting the suitable amount of theory information to the Boolean level. The core extractor is then called on the Boolean abstraction of the original SMT problem and of the theory lemmas. This results in an unsatisfiable core for the original SMT problem, once the remaining theory lemmas are removed. The approach is conceptually interesting, and has several advantages in practice. In fact, it is extremely simple to implement and to update, and it can be interfaced with every propositional core extractor in a plug-and-play manner, so as to benefit for free of all unsat-core reduction techniques which have been or will be made available. We have evaluated our algorithm with a very extensive empirical test on SMT-LIB benchmarks, which confirms the validity and potential of this approach.
Recommendations
- A Simple and Flexible Way of Computing Small Unsatisfiable Cores in SAT Modulo Theories
- Faster Extraction of High-Level Minimal Unsatisfiable Cores
- An approach for extracting a small unsatisfiable core
- A Scalable Algorithm for Minimal Unsatisfiable Core Extraction
- Towards a notion of unsatisfiable cores for LTL
Cited in
(18)- Semantic relevance
- Extracting unsatisfiable cores for LTL via temporal resolution
- \textsc{OptiMathSAT}: a tool for optimization modulo theories
- Towards a notion of unsatisfiable and unrealizable cores for LTL
- Enhancing unsatisfiable cores for LTL with information on temporal relevance
- Optimization modulo theories with linear rational costs
- Randomized algorithms for finding the shortest negative cost cycle in networks
- Counterexample-guided prophecy for model checking modulo the theory of arrays
- An approach for extracting a small unsatisfiable core
- Towards a notion of unsatisfiable cores for LTL
- Finding connections via satisfiability solving
- Satisfiability modulo theories
- Counterexample-Guided Prophecy for Model Checking Modulo the Theory of Arrays
- Satisfiability modulo theories and chiral heterotic string vacua with positive cosmological constant
- On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations
- Scalable algorithms for abduction via enumerative syntax-guided synthesis
- Conflict-free electric vehicle routing problem: an improved compositional algorithm
- A Simple and Flexible Way of Computing Small Unsatisfiable Cores in SAT Modulo Theories
This page was built for publication: Computing small unsatisfiable cores in satisfiability modulo theories
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2996914)
