Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.05537 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918430917001216 |
|---|---|
| author | Capelli, Florent Choi, YooJung Mengel, Stefan Muñoz, Martín Broeck, Guy Van den |
| author_facet | Capelli, Florent Choi, YooJung Mengel, Stefan Muñoz, Martín Broeck, Guy Van den |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_05537 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A canonical generalization of OBDD Capelli, Florent Choi, YooJung Mengel, Stefan Muñoz, Martín Broeck, Guy Van den Artificial Intelligence Data Structures and Algorithms 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. |
| title | A canonical generalization of OBDD |
| topic | Artificial Intelligence Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.05537 |