Write a Blog >>
POPL 2021
Sun 17 - Fri 22 January 2021 Online
Tue 19 Jan 2021 18:45 - 19:00 at VMCAI - Decision Procedures Chair(s): Alexander J. Summers

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 Jan

Displayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

18:30 - 19:30
Decision ProceduresVMCAI at VMCAI
Chair(s): Alexander J. Summers University of British Columbia
18:30
15m
Talk
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
15m
Talk
Incremental Search for Conflict and Unit Instances of Quantified Formulas with E-Matching
VMCAI
Jochen Hoenicke University of Freiburg, Tanja Schindler University of Freiburg
Media Attached
19:00
15m
Talk
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
15m
Talk
Compositional Satisfiability Solving in Separation Logic
VMCAI
Quang Loc Le University College London, UK
Media Attached