| Title: |
Counting Reduced Ordered Binary Decision Diagrams With Respect to Size |
| Authors: |
Clément, Julien; Genitrini, Antoine |
| Contributors: |
Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC); Université de Caen Normandie (UNICAEN); Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN); Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS); Equipe AMACC - Laboratoire GREYC - UMR6072; Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN); Algorithmes, Programmes et Résolution (APR); LIP6; Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS); ANR-23-CE48-0014,PANDAG,Analyse de paramètres de classes de DAGS(2023) |
| Source: |
ISSN: 1529-3785. |
| Publisher Information: |
CCSD; Association for Computing Machinery |
| Publication Year: |
2026 |
| Subject Terms: |
Boolean Function; Reduced Ordered Binary Decision Diagram; Enumerative Combinatorics; Directed Acyclic Graph; [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] |
| Description: |
International audience ; The set of binary decision diagrams, an efficient data structure representing Boolean functions, is extensively used in many distinct contexts like model verification, machine learning, cryptography or 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 specific compaction of a complete decision tree. A great 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. Recall the number of Boolean functions with k variables is equal to 2 2 k , which is of double exponential growth with respect to the number of variables. The maximal size of an robdd with k variables is M k ≈ 2 k /k. 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. It performs O(k n 3 log n) arithmetical operations on integers and necessitates to store O(n 2 ) integers in memory storage. Our new approach relies on a decomposition of robdds layer by layer and on an enumerative inclusion-exclusion argument. |
| Document Type: |
article in journal/newspaper |
| Language: |
English |
| DOI: |
10.1145/3799237 |
| Availability: |
https://hal.sorbonne-universite.fr/hal-05183438; https://hal.sorbonne-universite.fr/hal-05183438v2/document; https://hal.sorbonne-universite.fr/hal-05183438v2/file/ClementGenitrini.pdf; https://doi.org/10.1145/3799237 |
| Rights: |
https://creativecommons.org/licenses/by/4.0/ ; info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.7AB301D6 |
| Database: |
BASE |