Quantifizierte Boolesche Formeln: Komplexität und Modellierung

• Antragsteller: Professor Dr. Hans Kleine Büning
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 52589233

Ziel des Projektes ist es, ein besseres Verständnis quantifizierter Boolescher Formeln im Hinblick auf die Modellierung und die effiziente Verarbeitung zu erreichen. Im Einzelnen stehen dabei Fragen der Ausdrucksmächtigkeit von Teilklassen quantifizierter Boolescher Formeln mit freien Variablen, der Charakterisierung minimal falscher Formeln mit fester Deficiency und die Erweiterung von quantifizierten Booleschen Formeln um partiell geordnete Quantoren im Vordergrund. Aus methodischer Sicht wird hier weitgehend eine modelltheoretische Herangehensweise verfolgt.

• DFG-Verfahren: Sachbeihilfen