Description
Date depot: 14 mars 2022
Titre: The Combinatorics of Binary Decision Diagrams
Directeur de thèse:
Antoine GENITRINI (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Algorithmique, combinatoire
Resumé: Our project consists of an algorithmic and quantitative study of classical data structures from computer science under the prism of combinatorics. In the last decade many improvements have been achieved in order to characterize the associated directed acyclic graphs (or DAGs) combinatorially, paving the way for the analysis of objects induced by compaction procedures. In particular, we will focus on decision diagrams, representing Boolean functions.
A line of studies is based on a constructive way to handle the DAGs. The term constructive here means that no use of the inclusion-exclusion principle is necessary. The first paper by De Felice and Nicaud [FN13] aims at deriving an efficient algorithm to sample objects in the special class of deterministic acyclic automata. Another paper by Genitrini et al. [GPV21] presents another constructive enumeration and an effective uniform sampling for DAGs.
Using all these notions together, we are now ready to analyze properties of large random DAGs used at different places in computer science. Our expertise lies in analysis of algorithms using analytic and enumerative combinatorics in order to structurally describe combinatorial objects, to find new specifications and to exhibit universal properties of data structures.
In this PHD project we aim at studying DAGs structures obtained through the compaction of trees using common substructures sharing. We plan to extend the general methodology to classical families of DAGs, that can still be seen as compacted structures. Our main focus is on studying typical structure of DAGs obtained by compaction from a combinatorial point of view. Thus we are interested in enumeration, random sampling and probabilistic analysis with the help of tools from combinatorics and probability theory.