A canonical generalization of OBDD

Florent Capelli, YooJung Choi, Stefan Mengel, Martín Muñoz, Guy Van den Broeck · 2026

Read A canonical generalization of OBDD by Florent Capelli, YooJung Choi, Stefan Mengel, Martín Muñoz, Guy Van den Broeck (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-05537.txt.

Introduction

Capelli and four colleagues introduce Tree Decision Diagrams, a Boolean-function model generalizing ordered binary decision diagrams. TDDs keep the same tractable operations, counting, enumeration, conditioning, and apply, while staying more succinct. Formulas of treewidth k fit in fixed-parameter tractable size, which ordered diagrams cannot match, and the authors map bottom-up compilation cost to factor width.

Catalog record

CREATORFlorent Capelli, YooJung Choi, Stefan Mengel, Martín Muñoz, Guy Van den Broeck
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57612
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.05537

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A canonical generalization of OBDD Florent Capelli, YooJung Choi, Stefan Mengel, Martín Muñoz, Guy Van den Broeck 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 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 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. Univ. Artois, CNRS, UMR 8188, CRIL, F-62300 Lens, [email protected]://orcid.org/0000-0002-2842-8223Arizona State [email protected]://orcid.org/0009-0009-8102-4170 Univ. Artois, CNRS, UMR 8188, CRIL, F-62300 Lens, [email protected]://orcid.org/0000-0003-1386-8784 Univ. Artois, CNRS, UMR 8188, CRIL, F-62300 Lens, [email protected]://orcid.org/0009-0003-3294-6159 University of California, Los [email protected]://orcid.org/0000-0003-3434-2503 ccs Computing methodologies Knowledge representation and reasoning ccs Theory of computation Constraint and logic programming keywords Knowledge Compilation † † runningauthor: F. Capelli, Y. Choi, S. Mengel, M. Muñoz and G. Van den Broeck † † copyright: Florent Capelli, YooJung Choi, Stefan Mengel, Martín Muñoz and Guy Van den Broeck † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Knowledge compilation is the systematic study of different representations of knowledge, often in the form of Boolean functions, but also for preferences [ 23 ] , actions in planning [ 28 ] , product configuration [ 35 , 7 ] , databases [ 25 ] , etc. To compare different data structures representing the same type of data, following the groundbreaking work of Darwiche and Marquis [ 19 ] , one analyzes them with respect to a list of potential desirable properties that they might have, generally a set of tractable operations and queries on them. There is a general observed trade-off between usefulness (what can one do efficiently with a data structure?) and succinctness (how small is the representation in a specific form?): on one end of the spectrum, there are representations like OBDD that allow many useful operations, but are rather verbose. On the other end, there are, e.g., DNNF that are far more succinct but allow only few operations efficiently. Knowledge compilation explores the space between these two extremes and aims to provide representation languages with different trade-offs for different applications. One important operation in knowledge compilation is the so-called apply operation which is, given two representations of the same format, to compute a representation of a target Boolean combination, most importantly, their conjunction. The most prominent knowledge compilation languages that support this operation efficiently are OBDD [ 15 ] and SDD [ 21 ] . The apply operation is of special practical importance because it is often used as the basis of bottom-up compilation of systems of constraints into a different target representation. The idea is to first compile the individual constraints into the target format and then iteratively conjoin them with the apply operation. In particular, this is the most common approach for constructing OBDD [ 34 ] and SDD [ 16 ] . To avoid size blow-ups during bottom-up compilation, it is common to try to shrink the currently compiled form, which for OBDD is possible because they can be turned into a canonical minimal form, i.e., a form of minimal size and unique, up to isomorphism, among all equivalent OBDD with the same variable order. Canonicity is also useful to efficiently test equivalence between two given OBDD. For SDD, which are in general exponentially smaller than OBDD [ 14 ] , the situation is more complicated [ 38 ] : while they have a canonical form, it is not minimal—in fact, it can be exponentially larger than the smallest equivalent SDD. Moreover, canonical SDD are not stable under conjunction, as the conjunction of two canonical SDD can become exponentially larger than each after canonization. In this paper, we introduce and analyze a new knowledge compilation language which we call Tree Decision Diagrams (TDD). We show that TDD have various desirable properties of OBDD, such as having an efficient apply algorithm, a canonical form that is also minimal, and an efficient algorithm to find it for any given non-minimal TDD. We show that, as is the case for OBDD, the size of a canonical TDD can be characterized by certain subfunction counts which gives a very clean understanding of which functions can efficiently be compiled into a TDD. We highlight that, in contrast to SDD, canonical TDD can be efficiently combined via apply into a new canonical TDD. Since TDD have efficient apply and minimization algorithms, they are a good target language for bottom-up compilation. As a proof of concept, we present a simple algorithm that allows compiling CNF formulas and circuits of bounded treewidth efficiently. While compilation results in this setting were known before [ 20 , 27 , 12 , 4 , 13 ] , our approach compiles into a more restricted language with better properties. We highlight that these results had rather involved dynamic programming solutions, in contrast to our compilation algorithm which simply performs apply and minimization in a bottom-up fashion. Our results depend on the characterization by subfunction counts. However, crucially, this argument is only used in the analysis and not in the algorithm. The paper is organized as follows: \cref sec:prelim introduces necessary preliminaries. \cref sec:prop:dd defines the notion of TDD, \cref sec:transformations presents the transformations that are tractable for TDDs. \cref sec:prop:minimization contains the minimization procedures for TDD and shows that they are canonical. \cref sec:prop:struct-cnf establishes bottom-up compilation of TDD and uses it to compile bounded treewidth formulas and circuits. Finally, \cref sec:prop:tdd-vs-rest compares TDDs with other representation languages. Due to page limit, we moved most of the proofs to the appendix. Statements whose proof can be found in this appendix are marked with a (\star) symbol. 2 Preliminaries Assignments and Boolean functions. Given two sets A and B , we denote by B^{A} the set of functions from A to B . When B=\{0,1\} , we will often write 2^{A} to denote the set of assignments from a set A to \{0,1\} . An element \tau\in 2^{A} is called a Boolean assignment over variables A , and we will often just write “assignment” when it is clear from context that it is Boolean. A partial (Boolean) assignment over variables X is an element of 2^{Y} for some Y\subseteq X . Given two assignments \tau_{1}\in 2^{X} and \tau_{2}\in 2^{Y} with X\cap Y=\emptyset , we denote by \tau_{1}\times\tau_{2} the assignment over variables X\cup Y such that (\tau_{1}\times\tau_{2})(z)=\tau_{1}(z) if z\in X and (\tau_{1}\times\tau_{2})(z)=\tau_{2}(z) if z\in Y . We denote by \langle x/0\rangle (resp. \langle x/1\rangle ) the assignment in 2^{\{x\}} mapping x to 0 (resp. to 1 ). We will also use

Read the complete text