Binary decision diagrams are a family of data structures that can be used to efficiently represent a Boolean function. They were popularized by Randal Bryant in 1986 and have since been used in numerous applications.
In this presentation, we will address some counting issues related to these structures, focusing on the best-known variant, called reduced ordered decision diagram (ROBDD). The main result is to provide a polynomial algorithm for calculating the number of ROBDDs with \(k\) variables of size \(n\) (the size being the number of decision nodes in the structure). After much effort, we were able to apply the method for 16 variables (it is important to remain modest).
As an application of these results, we propose the first polynomial method for uniform random generation (for size) of ROBDDs.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne