Parameteranalyse für bestimmte gerichtete azyklische Graphen

DAGs sind Objekte, die aus Knoten und gerichteten Kanten; jede Kante verbindet ihren Startknoten mit ihrem Endknoten, in dieser Reihenfolge; und es darf keine Wege von einem Knoten zu sich selbst geben. Eine DAG-Klasse ist eine Zusammenfassung von DAGs, die zusätzliche kontextabhängige Bedingungen erfüllen. DAGs fallen in die allgemeine Klasse der diskreten Strukturen. Viele DAG-Klassen dienen als Datenstrukturen in verschieden Bereichen der Informatik. Da Algorithmen auf Datenstrukturen arbeiten, liefert die Kenntnis der typischen Form einer speziellen Datenstruktur, zB einer Klasse von DAGs, Informationen über die Qualität von Algorithmen. Der kombinatorische Ansatz zur Formanalyse diskreter Strukturen ist durch Abzählen: Der Wert einer Eigenschaft wird festgelegt und dann zählt man, wie viele Objekte einer bestimmten Größe es gibt, bei denen der Parameters den vorgegebenen Wert hat. Dies liefert dann Informationen über die typische Größe des Parameters oder deren Verteilung. Dieses Projekt untersucht DAG-Klassen, die aus Kompaktifizierungssprozessen hervorgehen. Unter so einem Prozess verstehen wir ein Verfahren, um Speicherplatz zu sparen, indem wir gleiche Teile eines Objekts nur einmal speichern und für die weiteren Vorkommen Zeiger verwenden. Es gibt mehrere DAG-Klassen, die noch nie mit dem kombinatorischen Ansatz behandelt wurden. Zwei dieser Klassen sind Boolesche Schaltkreise und Varianten von binären Entscheidungsdiagrammen (BED`s). Beide gehen von einer ursprünglich baumartigen Struktur aus, die dann kompaktifiziert wird. Eine andere vor allem theoretisch interessante Klasse sind monoton markierte Bäume. Das sind baumartige Strukturen, die einem generischen Wachstumsprozess entsprechen und deren Knoten so mit Zahlen markiert werden, dass die Zahlen entlang jedes von der Wurzel ausgehenden Pfades größer werden. In der Literatur finden sich viele Klassen solcher Strukturen. Lassen wir Wiederholungen der Markierungen zu, so können wir sie als DAGs auffassen. Boolesche Schaltkreise bzw BED`s werden verwendet, um Boolesche Funktionen darzustellen, d.h. Funktionen, die für jede ihrer Eingangsvariablen sowie für die Ausgangsvariable "Wahr" oder "Falsch" annehmen. Ihre Analyse soll zu Erkenntnissen über die strukturellen Eigenschaften dieser Funktionen führen. Kombinatorisches Abzählen erfordert eine geeignet gestaltete formale Beschreibung der Strukturen, genannt Spezifikation. Deren Bausteine können in Funktionen und algebraische Operationen übersetzt werden, die dann mit zahlreichen mathematischen Methoden analysiert werden können. Für einige unserer Strukturen ist keine Spezifikation bekannt, und eine solche verwendet vermutlich ungewöhnliche Operationen, die die Entwicklung einer neuen Funktionsalgebra erfordern. Es wird erwartet, dass dies breiter anwendbar ist. Im besten Fall gelingt eine Vereinheitlichung dieser kompakten Strukturen, die dann eine einheitliche Analyse ermöglicht.