Zusammenhang zwischen Hierarchien in Komplexitätstheorie, Automatentheorie, Theorie der Formalen Sprachen und Logik

• Antragsteller: Professor Dr. Klaus W. Wagner
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 1999 bis 2005
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5149736

Das Projekt verbindet verschiedene Gebiete der Theoretischen Informatik, nämlich die Theorie der Formalen Sprachen, Algebra, Logik, Automatentheorie und Komplexitätstheorie. Aus der Literatur sind bereits, zum Teil seit langem, strukturelle Beziehungen zwischen Klassen regulärer Mengen auf der einen Seite und Varietäten von Monoiden, Teilklassen logischer Nachfolger- und Ordnungstheorien, Klassen endlicher Automaten und Komplexitätsklassen zwischen P und PSPACE auf der anderen Seite untersucht worden. Vor allem gibt es interessante Beziehungen zwischen Hierarchien in diesen verschiedenen Gebieten (z.B.: Dot-Depth-Hierarchie - Quantorenhierarchie der Nachfolgertheorie der ersten Stufe - Polynomialzeithierarchie). Doch viele wichtigen Fragen in den einzelnen Gebieten sind in diesem Zusammenhang noch offen (z.B. Entscheidbarkeit der Klassen der Dot-Depth-Hierarchie, Struktur wichtiger Komplexitätsklassen in PSPACE). Durch das Herausfinden weiterer Beziehungen zwischen den Gebieten sollen Beiträge zur Lösung dieser Probleme geleistet werden. Methodisch soll vor allem eine weitere strukturelle Analyse der endlichen Automaten im Vordergrund stehen.

• DFG-Verfahren: Sachbeihilfen