Parameter analysis of certain classes of DAGs

In general, a DAG is a mathematical object that is composed of vertices and directed edges. Each edge connects its start vertex to its end vertex, in that direction. Finally, when walking on the edges along their directions, there must not be a way to walk from a vertex to itself. A class of DAGs is a collection of DAGs that satisfies additional conditions. It belongs to the wider class of objects known as discrete structures. Many classes of DAGs serve as data structures in various contexts of computer science. As algorithms manipulate or work on data structures, the typical shape of a data structure from some class, e.g. a class of DAGs, reveals information about the quality of algorithms. The combinatorial approach to the shape analysis of discrete structures is by counting: The value of the shape characteristic under consideration is fixed and then one counts how many objects are there having a specified size and the given value of the shape parameter. This gives then information about the typical size or the size distribution of the shape parameter. This project focuses on classes of DAGs that originate from compaction processes. By a compaction process we mean a way to save storage by looking for identical parts of an object (a data structure) and storing only one instance in memory and using pointer to that instance for the further occurrences. There are several classes of DAGs that have never been approach with by combinatorial methods. Two such classes are Boolean circuits and derivates of binary decision diagrams (bdd`s). Both originate from an initially tree-like structure that is then compacted. Another class, that is mainly of theoretical interest, is increasingly labelled trees. Here we start from a tree- like structure corresponding to some generic growth process and with vertices labelled by numbers in a way that numbers grow on each path starting at the root of the tree and moving away from it. Many classes of such structures appear in the literature, but when allowing repetitions, we can see them actually as DAGs and enter new ground then. Boolean circuits bdd`s are used to represent Boolean functions, i.e. functions that take "True" or "False" for each of their input variables as well as the output variable. Their analysis will lead to insight of structural properties of those functions. The combinatorial approach is not direct, but needs a suitably designed formal description of the considered structures, called specification. Having that, we can translate its building blocks into functions and algebraic operations on them, and then analyze it with numerous mathematical methods. For some of our structures, a specification is unknown, and if found, it may use unusual building operations that require the development of new function algebra. It is expected that this is wider applicable and, in the best case, puts all those compacted structures under a common roof, allowing a uniform way of analysis.