On limitations of structured (deterministic) DNNFs

DOI10.1007/s00224-019-09960-wzbMath1446.68152OpenAlexW2993167090MaRDI QIDQ778525

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

ordered binary decision diagramscomplexity theoryknowledge compilationdecomposable negation normal formssentential decision diagrams

Mathematics Subject Classification ID

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

Related Items

On the relation between structured \(d\)-DNNFs and SDDs

Cites Work

• Unnamed Item
• Unnamed Item
• On the read-once property of branching programs and CNFs of bounded treewidth
• Knowledge compilation meets database theory: compiling queries to decision diagrams
• On the relative succinctness of sentential decision diagrams
• On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Graph-Based Algorithms for Boolean Function Manipulation
• On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
• Branching Programs and Binary Decision Diagrams
• Decomposable negation normal form