On the relation between structured d-DNNFs and SDDs

DOI10.1007/S00224-020-10003-YMaRDI QIDQ2035477zbMATH OpenOpenAlexFDO

Authors Beate Bollig, Martin Farenholtz

Publication date 24 June 2021

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1912.01430

zbMATH Keywords

complexity theoryknowledge compilationdecomposable negation normal formssentential decision diagrams

Mathematics Subject Classification ID

Data structures (68P05) Knowledge representation (68T30)

Recommendations

• On limitations of structured (deterministic) DNNFs
• On the relative succinctness of sentential decision diagrams
• On compiling CNFs into structured deterministic DNNFs
• Top-down algorithms for constructing structured DNNF: theoretical and practical implications
• Decomposable negation normal form

Cites work

• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 1946853 (Why is no real title available?)
• Branching Programs and Binary Decision Diagrams
• Decomposable negation normal form
• On compiling structured CNFs to OBDDs
• On limitations of structured (deterministic) DNNFs
• On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• On the relative succinctness of sentential decision diagrams
• Top-down algorithms for constructing structured DNNF: theoretical and practical implications

Cited in

(5)

• DAG-\( \Sigma \): a DAG-based sigma protocol for relations in CNF
• On the relative succinctness of sentential decision diagrams
• Top-down algorithms for constructing structured DNNF: theoretical and practical implications
• On limitations of structured (deterministic) DNNFs
• An Abstract CNF-to-d-DNNF Compiler Based on Chronological CDCL

This page was built for publication: On the relation between structured \(d\)-DNNFs and SDDs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2035477)