Branching Programs and BDDs: Complexity and Efficient Algorithms

• Applicant: Professor Dr. Ingo Wegener (†)
• Subject Area: Theoretical Computer Science
• Term: from 2000 to 2004
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5261496

Branchingprogramme und BDDs bilden eine Darstellungform für Boolesche Funktionen. In ihrer allgemeinen Form sind sie seit langem in der Komplexitätstheorie behandelt worden, da ihre Größe ein Maß für den Platzbedarf nicht uniformer Rechner ist und die Größe zwischen Schaltkreisgröße und Formelgröße liegt. Eingeschränkte Modelle haben zahlreiche Anwendungen als Datenstruktur für Boolesche Funktionen gefunden, z.B. in Verifikation, Model Checking und CAD-Anwendungen. Die Theorie zu Branchingprogrammen und BDDs soll ausgebaut werden, indem für konkrete Funktionen und Modelle untere und obere Größenschranken bewiesen werden, das typische Verhalten von OBDDs untersucht wird, nichtdeterministische und randomisierte BDD-Varianten betrachtet werden und BDDs zur approximativen Darstellung von Funktionen verwendet werden. Darüber hinaus sollen Bezüge zu verwandten Fragestellungen hergestellt werden. Bei den Problemstellungen wollen wir uns von Fragen aus den Anwendungen motivieren lassen und Ergebnisse anstreben, die neben ihrem theoretischen Wert die Bezüge zu den Anwendungen nicht vermissen lassen.

• DFG Programme: Research Grants