A canonical generalization of OBDD
This work provides a more efficient data structure for Boolean function representation, benefiting areas like automated reasoning and verification, though it is incremental as it builds on existing OBDD and d-DNNF frameworks.
The authors tackled the problem of representing Boolean functions more succinctly than OBDDs by introducing Tree Decision Diagrams (TDDs), showing that TDDs maintain tractability properties like model counting and can represent CNF formulas of treewidth k with fixed-parameter tractable size, which OBDDs cannot achieve.
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.