Das Modell der Restart-Automaten gibt es seit etwa 15 Jahren. Durch die Ausstattung mit verschiedenen Berechnungsressourcen und die Auferlegung von Einschränkungen an die Arbeitsweise entstand mit der Zeit ein unfangreiches System von Automatentypen mit stark unterschiedlicher generativer Mächtigkeit.
Ziel dieser Arbeit ist es, Restart-Automaten in ihrer Effizienz bei der Beschreibung von Sprachen mit der von konventionellen Automatenmodellen und Grammatiken, sowie untereinander, zu vergleichen.
Die Schwerpunkte liegen zum einen auf dem Vergleich von Beschreibern regulärer Sprachen (Zustandskomplexität) und zum anderen auf dem Nachweis nichtrekursiver trade-offs (in Bezug auf die Beschreibungskomplexität) zwischen den mächtigeren Sprachklassen.
Im Rahmen des ersten Schwerpunkts werden die Systeme NFA, DFA, AFA (nichtdeterministische, deterministische und alternierende endliche Automaten) mit den beiden Restart-Automaten-Typen R(1) und det-RR(1) verglichen, die ebenfalls Akzeptoren für reguläre Sprachen sind (der Nachweis dieser Eigenschaft von det-RR(1)-Automaten ist ebenfalls Bestandteil dieser Arbeit).
Für die Untersuchungen im Rahmen des zweiten Schwerpunkts werden zusätzlich einige Nachweise bezüglich der (Nicht-)Erkennung von valid-computations Sprachen, sowie einiger nicht-semi-entscheidbarer Eigenschaften geführt.
Verknüpfung zu Publikationen oder weiteren Datensätzen
