Kurzfassung

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
...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.» weiterlesen» einklappen