On the relative succinctness of sentential decision diagrams

DOI10.1007/s00224-018-9904-zzbMath1435.68320arXiv1802.04544OpenAlexW2963539719WikidataQ128787747 ScholiaQ128787747MaRDI QIDQ2322709

Matthias Buttkus, Beate Bollig

Publication date: 5 September 2019

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

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

zbMATH Keywords

ordered binary decision diagramscomplexity theoryknowledge compilationdecomposable negation normal formssentential decision diagramsstorage access functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Data structures (68P05)

Related Items

On the (complete) reasons behind decisions ⋮ On the relation between structured \(d\)-DNNFs and SDDs ⋮ On the relative succinctness of sentential decision diagrams ⋮ On limitations of structured (deterministic) DNNFs ⋮ Connecting knowledge compilation classes and width parameters ⋮ On Quantifying Literals in Boolean Logic and its Applications to Explainable AI

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the read-once property of branching programs and CNFs of bounded treewidth
• On the size of binary decision diagrams representing Boolean functions
• Graph driven BDDs -- a new data structure for Boolean functions
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
• Efficient data structures for Boolean functions
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• 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
• Communication Complexity
• A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton
• Decomposable negation normal form

This page was built for publication: On the relative succinctness of sentential decision diagrams