Search papers, labs, and topics across Lattice.
This paper introduces Tree Decision Diagrams (TDDs), a generalization of Ordered Binary Decision Diagrams (OBDDs) that are a restricted form of structured Decomposable Negation Normal Form (d-DNNF) respecting a vtree. TDDs maintain the tractability properties of OBDDs for tasks like model counting and enumeration, while achieving more succinct representations, particularly for CNF formulas with bounded treewidth. The authors also analyze the complexity of compiling CNF formulas into deterministic TDDs using a bottom-up approach, connecting it to the factor width of the formula.
CNF formulas with treewidth *k* can be represented by Tree Decision Diagrams (TDDs) with FPT size, something provably impossible for OBDDs.
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.
