A canonical generalization of OBDD
2026/04/07 by Florent Capelli, YooJung Choi, Stefan Mengel +2 · 6 voices
#cs.AI #cs.DS
paper · pdf
Abstract
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.
Discussions
- A Canonical Generalization of OBDD [hn, 26 points, 14 comments]
- A Canonical Generalization of OBDD https://arxiv.org/abs/2604.05537 (https://news.ycombinator.com/item?id=47747595) [bsky, 0 points, 0 comments]
- A Canonical Generalization of OBDD https://arxiv.org/abs/2604.05537 [bsky, 0 points, 0 comments]
- A new decision diagram appears! We introduce Tree Decision Diagrams (TDD) as a model for Boolean functions that generalizes OBDD. … We show that TDDs enjoy the same tractability properties as OBDD, su [bsky, 0 points, 0 comments]
- Discover the groundbreaking insights in the canonical generalization of Ordered Binary Decision Diagrams (OBDD). This research pushes the boundaries of computational efficiency and opens new avenues f [bsky, 0 points, 0 comments]
- A Canonical Generalization of OBDD https:// arxiv.org/abs/2604.05537 # arxiv [mastodon, 0 points, 0 comments]
Related