Detailseite
Projekt
Moderne Komplexitätsaspekte formaler Sprachen
Antragsteller
Professor Dr. Henning Fernau
Fachliche Zuordnung
Theoretische Informatik
Förderung
Förderung von 2018 bis 2023
Projektkennung
Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 407073110
Formale Sprachen sind eines der grundlegenden Gebiete der Theoretischen Informatik. Viele wichtige Aspekte informatischer Anwendungen lassen sich hiermit modellieren und auch zahlreiche algorithmische Fragen lassen sich in diesem Kontext stellen und lösen. So kann dieser Zweig der Informatik auf eine mittlerweile über sechzigjährige Geschichte zurückblicken.Dessen ungeachtet gibt es immer noch ungelöste Fragen, häufig kombinatorischer Natur, wie die Vermutung von Cerny über die Länge sogenannter synchronisierender Wörter. Da die meisten Fragestellungen in diesem Bereich mittlerweile als „klassisch“' gelten, wurden diese unserem Empfinden nach weitgehend vernachlässigt, als in der letzten Dekade viele neue komplexitätstheoretische Konzepte entwickelt wurden. So wurden mehr und mehr NP-harte Probleme (also Probleme, die vermutlich nicht effizient auf Rechnern gelöst werden können) dahingehend untersucht, ob sie durch Betrachten geeigneter Parameter in die Klasse FPT fallen. Dies würde bedeuten, dass sie doch (für kleine Parametergrößen) effizient lösbar wären. Gleichfalls wurde untersucht, ob sie z.B. sogenannte subexponentielle exakte Algorithmen gestatten (oder dies unter Zugrundelegen der Exponentialzeithypothese (ETH) nicht erlauben). Ein weiterer moderner Forschungszweig der Theoretischen Informatik ist die feinkörnige Komplexität. Hier geht es insbesondere darum, Optimalität von effizienten, also Polynomzeit-Algorithmen (bis auf polylogarithmische Faktoren) nachzuweisen. All diese modernen Aspekte der Komplexitätstheorie werden heutzutage gerne auf führenden internationalen Konferenzen gesehen, aber kaum im Zusammenhang mit formalsprachlichen Fragestellungen untersucht. Das wollen wir mit diesem Projekt ändern.Grundsätzliches Ziel dieses Projektes soll es sein, moderne komplexitätstheoretische Methoden und Ansätze, wie parametrisierte Komplexität, (S)ETH-basierte Schranken und allgemeiner feinkörnige Komplexitätsüberlegungen, auf formalsprachliche Fragestellungen anzuwenden, da, wie eingangs erwähnt, diese Fragestellungen immer noch eine der Grundlagen der Informatik darstellen und weiterhin vielfach im praktischen Einsatz sind. Wir erwähnen nur exemplarisch Compilerbau, Texteditoren, Datenkompression und Suchmaschinen.
DFG-Verfahren
Sachbeihilfen
Internationaler Bezug
Russische Föderation, USA
