Combinatorics of reduced ordered binary decision diagrams. Application to random uniform sampling

Any Boolean function corresponds to a complete full binary decision tree. This tree can in turn be represented in a maximally compact form as a directed acyclic graph where common subtrees are factored and shared, keeping only one copy of each unique subtree. This yields the celebrated and widely used structure called reduced ordered binary decision diagram (ROBDD). In the random uniform model over the set of Boolean functions with a fixed number of variables the size of a typical ROBDD is of near maximal (exponential) size. This makes random sampling of small ROBDDs (the ones usable in practice) a difficult task even for a few variables. In this talk we want to compute the distribution of ROBDDs (for a fixed number of variables) with respect to the size. As a by-product we get a random uniform and exhaustive sampler for ROBDDs for a given number of variables and size with polynomial time complexity.

Joint work with Antoine Genitrini (LIP6, Paris).