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

• Applicant: Professor Dr. Klaus W. Wagner
• Subject Area: Theoretical Computer Science
• Term: from 1999 to 2005
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants