The 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 modeling of these data structures as directed acyclic graphs (or DAGs) combinatorially, paving the way for the analysis of objects induced by compaction procedures. Particular focus is on Boolean circuits and decision diagrams. The project thus considers new types of objects in the combinatorial setting. For some of them, even a proper specification is missing and it could be a major challenge to find one. A further challenge is to extend the generating function algebra to these new settings.

Although the methodology to be developed will be designed for the proposed problems, it is potentially widely applicable, in particular, since DAGs appear in many different applications. An ultimate breakthrough would be the identification of a general class of DAGs that is analytically tractable and creates a uniform framework for data structures that originate from any kind of compaction, presenting therefore a uniform way to analyse the most important shape characteristics of such structures.