2 Search Results for "Bryant, Randal"

Document
DOI: 10.4230/LIPIcs.SAT.2023.6
Certified Knowledge Compilation with Application to Verified Model Counting

Authors: Randal E. Bryant, Wojciech Nawrocki, Jeremy Avigad, and Marijn J. H. Heule

Published in: LIPIcs, Volume 271, 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)

Abstract
Computing many useful properties of Boolean formulas, such as their weighted or unweighted model count, is intractable on general representations. It can become tractable when formulas are expressed in a special form, such as the decision-decomposable, negation normal form (dec-DNNF) . Knowledge compilation is the process of converting a formula into such a form. Unfortunately existing knowledge compilers provide no guarantee that their output correctly represents the original formula, and therefore they cannot validate a model count, or any other computed value. We present Partitioned-Operation Graphs (POGs), a form that can encode all of the representations used by existing knowledge compilers. We have designed CPOG, a framework that can express proofs of equivalence between a POG and a Boolean formula in conjunctive normal form (CNF). We have developed a program that generates POG representations from dec-DNNF graphs produced by the state-of-the-art knowledge compiler D4, as well as checkable CPOG proofs certifying that the output POGs are equivalent to the input CNF formulas. Our toolchain for generating and verifying POGs scales to all but the largest graphs produced by D4 for formulas from a recent model counting competition. Additionally, we have developed a formally verified CPOG checker and model counter for POGs in the Lean 4 proof assistant. In doing so, we proved the soundness of our proof framework. These programs comprise the first formally verified toolchain for weighted and unweighted model counting.
Cite as

Randal E. Bryant, Wojciech Nawrocki, Jeremy Avigad, and Marijn J. H. Heule. Certified Knowledge Compilation with Application to Verified Model Counting. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 271, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bryant_et_al:LIPIcs.SAT.2023.6,
  author =	{Bryant, Randal E. and Nawrocki, Wojciech and Avigad, Jeremy and Heule, Marijn J. H.},
  title =	{{Certified Knowledge Compilation with Application to Verified Model Counting}},
  booktitle =	{26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-286-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{271},
  editor =	{Mahajan, Meena and Slivovsky, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2023.6},
  URN =		{urn:nbn:de:0030-drops-184685},
  doi =		{10.4230/LIPIcs.SAT.2023.6},
  annote =	{Keywords: Propositional model counting, Proof checking}
}
Document
DOI: 10.4230/DagSemRep.56
Computer Aided Design and Test (Dagstuhl Seminar 9307)

Authors: Bernd Becker, Randal Bryant, and Christoph Meinel

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Bernd Becker, Randal Bryant, and Christoph Meinel. Computer Aided Design and Test (Dagstuhl Seminar 9307). Dagstuhl Seminar Report 56, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1993)

Copy BibTex To Clipboard

@TechReport{becker_et_al:DagSemRep.56,
  author =	{Becker, Bernd and Bryant, Randal and Meinel, Christoph},
  title =	{{Computer Aided Design and Test (Dagstuhl Seminar 9307)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{1993},
  type = 	{Dagstuhl Seminar Report},
  number =	{56},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.56},
  URN =		{urn:nbn:de:0030-drops-149448},
  doi =		{10.4230/DagSemRep.56},
}
  • Refine by Author
  • 1 Avigad, Jeremy
  • 1 Becker, Bernd
  • 1 Bryant, Randal
  • 1 Bryant, Randal E.
  • 1 Heule, Marijn J. H.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Automated reasoning

  • Refine by Keyword
  • 1 Proof checking
  • 1 Propositional model counting

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 1993
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact