Papers › An iterative approach for counting reduced ordered binary decision diagrams
An iterative approach for counting reduced ordered binary decision diagrams
Julien Clément, Antoine Genitrini
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
For three decades binary decision diagrams, a data structure efficiently representing Boolean functions, have been widely used in many distinct contexts like model verification, machine learning, cryptography and also resolution of combinatorial problems. The most famous variant, called reduced ordered binary decision diagram (ROBDD for short), can be viewed as the result of a compaction procedure on the full decision tree. A useful property is that once an order over the Boolean variables is fixed, each Boolean function is represented by exactly one ROBDD. In this paper we aim at computing the exact distribution of the Boolean functions in k variables according to the ROBDD size}, where the ROBDD size is equal to the number of decision nodes of the underlying directed acyclic graph (DAG for short) structure. Recall the number of Boolean functions with k variables is equal to 2^(2ᵏ), which is of double exponential growth with respect to the number of variables. The maximal size of a ROBDD with k variables is Mₖ ≈2ᵏ / k. Apart from the natural combinatorial explosion observed, another difficulty for computing the distribution according to size is to take into account dependencies within the DAG structure of ROBDDs. In this paper, we develop the first polynomial algorithm to derive the distribution of Boolean functions over k variables with respect to ROBDD size denoted by n. The algorithm computes the (enumerative) generating function of ROBDDs with k variables up to size n. It performs O(k n⁴) arithmetical operations on integers and necessitates storing O((k+n) n²) integers with bit length O(nlogn). Our new approach relies on a decomposition of ROBDDs layer by layer and on an inclusion-exclusion argument.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections