Detailseite
Projekt Druckansicht

Branchingprogramme und BDDs: Komplexität und Effiziente Algorithmen

Antragsteller Professor Dr. Ingo Wegener (†)
Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2000 bis 2004
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren Sachbeihilfen
 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung