A canonical generalization of OBDD

Florent Capelli, YooJung Choi, Stefan Mengel, Martín Muñoz, Guy Van den Broeck
4/7/2026
cs.AIcs.DS

No confident code implementation found for this paper.

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Cite this paper

@article{capelli2026canonical,
  title  = {A canonical generalization of OBDD},
  author = {Florent Capelli and YooJung Choi and Stefan Mengel and Martín Muñoz and Guy Van den Broeck},
  year   = {2026},
  eprint = {2604.05537},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2604.05537v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2604.05537.svg)](https://codeofpaper.com/paper/2604.05537)

Discussion