https://www.dagstuhl.de/20483
22. – 27. November 2020, Event 20483
Moderne Aspekte der Komplexitätstheorie in der Automatentheorie
Organisatoren
Volker Diekert (Universität Stuttgart, DE)
Henning Fernau (Universität Trier, DE)
Petra Wolf (Universität Trier, DE)
Auskunft zu diesem Event erteilt
Beschreibung
Sowohl Automatentheorie wie auch Komplexitätstheorie gehören zu den klassischen Bausteinen der Informatik. Dennoch sind zahlreiche naheliegende Fragestellungen nicht durchgreifend untersucht, insbesondere, was neuere Entwicklungen in beiden Bereichen betrifft. Im Bereich der Komplexitätstheorie sind hier namentlich besonders die Parameterisierte Komplexität (und Algorithmik) sowie die feinkörnige (fine-grained) Komplexität zu nennen. Im Bereich der Automatentheorie betrifft das beispielsweise Quantencomputing mit der Ausprägung Quantenautomatenmodelle, aber auch mehr anwendungsorientierte Automatenmodelle, wie sie beispielsweise im Datenbankbereich benutzt werden. Schließlich ist es durchaus von Interesse, modernere Begriffe aus der Komplexitätstheorie auf klassische Begriffe aus der Automatentheorie anzuwenden oder umgekehrt eher klassische Begriffe aus der Komplexitätstheorie auf moderne Bereiche in der Automatentheorie.
Motivation text license Creative Commons BY 3.0 DE
Henning Fernau