On limitations of structured (deterministic) DNNFs

DOI10.1007/S00224-019-09960-WMaRDI QIDQ778525zbMATH OpenOpenAlexFDO

Authors Beate Bollig, Matthias Buttkus

Publication date 2 July 2020

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

Full work available at URL https://doi.org/10.1007/s00224-019-09960-w

zbMATH Keywords

complexity theoryordered binary decision diagramsknowledge compilationdecomposable negation normal formssentential decision diagrams

Mathematics Subject Classification ID

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

Recommendations

• On compiling CNFs into structured deterministic DNNFs
• On deterministic approximation of DNF
• On the relation between structured \(d\)-DNNFs and SDDs
• Top-down algorithms for constructing structured DNNF: theoretical and practical implications
• Limitations of lower bound methods for deterministic nested word automata
• scientific article; zbMATH DE number 4049104
• On the impossibility of structure-preserving deterministic primitives
• On the impossibility of structure-preserving deterministic primitives
• scientific article; zbMATH DE number 1332665
• Recognition of tractable DNFs representable by a constant number of intervals

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
• Graph-Based Algorithms for Boolean Function Manipulation
• Knowledge compilation meets database theory: compiling queries to decision diagrams
• On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
• On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• On the read-once property of branching programs and CNFs of bounded treewidth
• On the relative succinctness of sentential decision diagrams

Cited in

(5)

• On the relative succinctness of sentential decision diagrams
• Top-down algorithms for constructing structured DNNF: theoretical and practical implications
• An Abstract CNF-to-d-DNNF Compiler Based on Chronological CDCL
• On compiling CNFs into structured deterministic DNNFs
• On the relation between structured \(d\)-DNNFs and SDDs

This page was built for publication: On limitations of structured (deterministic) DNNFs

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