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.

Creative Commons BY 3.0 DE

Henning Fernau