Incremental Search for Conflict and Unit Instances of Quantified Formulas with E-Matching
We present a new method to find conflicting instances of quantified formulas in the context of SMT solving. Our method splits the search for such instances in two parts. In the first part, E-matching is used to find candidate instances of the quantified formulas. In principle, any existing incremental E-matching technique can be used for this part. The incrementality avoids duplicating work for every small change of the E-graph. Together with the candidate instance, E-matching also provides an existing node in the E-graph corresponding to every term in this instance. In the second part, these nodes are used to evaluate the candidate instance, i. e., without creating new terms. The evaluation can be done in constant time per instance. Our method detects conflicting instances and unit instances (unit instances are clauses that propagate new literals). This makes our method suitable for a tight integration into the DPLL(T) framework, very much in the style of an additional theory solver.
Tue 19 JanDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
18:30 - 19:30 | |||
18:30 15mTalk | Deciding the Bernays-Schoenfinkel Fragment over Bounded Difference Constraints by Simple Clause Learning over Theories VMCAI Martin Bromberger MPI-INF, Alberto Fiori Max Planck Institute for Informatics, Christoph Weidenbach MPI-INF Media Attached | ||
18:45 15mTalk | Incremental Search for Conflict and Unit Instances of Quantified Formulas with E-Matching VMCAI Media Attached | ||
19:00 15mTalk | On Pre- and Inprocessing for Weighted MaxSAT VMCAI Tobias Paxian University of Freiburg, Pascal Raiola University of Freiburg, Bernd Becker Albert-Ludwigs-University Freiburg Media Attached | ||
19:15 15mTalk | Compositional Satisfiability Solving in Separation Logic VMCAI Quang Loc Le University College London, UK Media Attached |