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

DOI10.1007/s00224-020-10003-yOpenAlexW3075905141MaRDI QIDQ2035477

Beate Bollig, Martin Farenholtz

Publication date: 24 June 2021

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

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• On limitations of structured (deterministic) DNNFs
• On the relative succinctness of sentential decision diagrams
• On compiling structured CNFs to OBDDs
• Top-Down Algorithms for Constructing Structured DNNF: Theoretical and Practical Implications
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
• Branching Programs and Binary Decision Diagrams
• Decomposable negation normal form

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