License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAT.2022.20
URN: urn:nbn:de:0030-drops-166941
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16694/
Go to the corresponding LIPIcs Volume Portal

Reichl, Franz-Xaver ; Slivovsky, Friedrich

Pedant: A Certifying DQBF Solver

pdf-format:
LIPIcs-SAT-2022-20.pdf (0.6 MB)

Abstract

Pedant is a solver for Dependency Quantified Boolean Formulas (DQBF) that combines propositional definition extraction with Counterexample-Guided Inductive Synthesis (CEGIS) to compute a model of a given formula. Pedant 2 improves upon an earlier version in several ways. We extend the notion of dependencies by allowing existential variables to depend on other existential variables. This leads to more and smaller definitions, as well as more concise repairs for counterexamples. Additionally, we reduce counterexamples by determining minimal separators in a conflict graph, and use decision tree learning to obtain default functions for undetermined variables. An experimental evaluation on standard benchmarks showed a significant increase in the number of solved instances compared to the previous version of our solver.

BibTeX - Entry

@InProceedings{reichl_et_al:LIPIcs.SAT.2022.20,
  author =	{Reichl, Franz-Xaver and Slivovsky, Friedrich},
  title =	{{Pedant: A Certifying DQBF Solver}},
  booktitle =	{25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)},
  pages =	{20:1--20:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-242-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{236},
  editor =	{Meel, Kuldeep S. and Strichman, Ofer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16694},
  URN =		{urn:nbn:de:0030-drops-166941},
  doi =		{10.4230/LIPIcs.SAT.2022.20},
  annote =	{Keywords: DQBF, DQBF Solver, Decision Procedure, Certificates}
}

Keywords: DQBF, DQBF Solver, Decision Procedure, Certificates
Collection: 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)
Issue Date: 2022
Date of publication: 28.07.2022
Supplementary Material: Software (Source Code): https://github.com/fslivovsky/pedant-solver

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI