A canonical generalization of OBDD
Not on the map. Why?
Abstract (arXiv)
We introduce Tree Decision Diagrams (TDD) as a model for Boolean functions that generalizes OBDD. They can be seen as a restriction of structured d-DNNF; that is, d-DNNF that respect a vtree T. We show that TDDs enjoy the same tractability properties as OBDD, such as model counting, enumeration, conditioning, and apply, and are more succinct. In particular, we show that CNF formulas of treewidth k can be represented by TDDs of FPT size, which is known to be impossible for OBDD. We study the complexity of compiling CNF formulas into deterministic TDDs via bottom-up compilation and relate the complexity of this approach with the notion of factor width introduced by Bova and Szeider.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 14 of its 44 references that are in the map. First posted on arXiv 7 Apr 2026.
Builds on
14 of 44 references.
References · 14
- 2020Probabilistic Circuits for Variational Inference in Discrete Graphical Modelscited by 20
- 2016SDDs are Exponentially More Succinct than OBDDscited by 19
- 2023Compositional Probabilistic and Causal Inference using Tractable Circuit Modelscited by 10
- 2018Connecting Knowledge Compilation Classes and Width Parameterscited by 9
- 2024Restructuring Tractable Probabilistic Circuitscited by 7
- 2013Lower Bounds for Exact Model Counting and Applications in Probabilistic Databasescited by 5
- 2017A Circuit-Based Approach to Efficient Enumerationcited by 3
- 2017Circuit Treewidth, Sentential Decision, and Query Compilationcited by 2
- 2019On the relation between structured d-DNNFs and SDDscited by 2
- 2025Compilation and Fast Model Counting beyond CNFcited by 2
- 2014Solving MaxSAT and #SAT on structured CNF formulascited by 1
- 2014No small nondeterministic read-once branching programs for CNFs of bounded treewidthcited by 1
Built on by
Not cited yet.