Ordered Restarting Automata

In der folgenden Arbeit geht es um geordnete Restartautomaten. Restartautomaten sind ein theoretisches Modell, das in der Linguistik bei der Analyse durch Reduktion Verwendung findet. Die geordneten Restartautomaten wurden im Zusammenhang von zweidimensionalen Bildsprachen eingeführt und bilden das zugrundeliegende eindimensionale Modell. Von diesem eindimensionalen Modell betrachten wir verschiedene Varianten und untersuchen und vergleichen hauptsächlich Sprachklassen und Beschreibungskomplexität. Eine Gemeinsamkeit all dieser Varianten ist die feste Fenstergröße von 3, und dass beim Schreiben das mittlere Zeichen durch ein kleineres Zeichen ersetzt wird. Wir untersuchen zunächst die Modelle, bei der Schreibvorgang immer gleichzeitig mit einem Restart verbunden ist. Ausgehend von deterministischen Modell mit Zuständen betrachten wir recht bald die zustandslose Variante, da diese ebenso die regulären Sprachen charakterisiert. Damit haben wir eine Charakterisierung der regulären Sprachen, die ähnlich einfach ist, wie die eines DEA. Statt der Zustände haben wir Bandsymbole. Zusätzlich können wir viele Sprachen und auch Sprachoperation deutlich prägnanter darstellen. Zudem geben wir ausgehend von einem zustandslosen geordneten Restartautomaten, der sowohl deterministisch als auch nicht-deterministisch sein darf, eine allgemeine Konstruktion für einen NEA mit exponentiell vielen Zuständen an, der die selbe Sprache beschreibt, und zeigen dass die Konstruktion bis auf eine Konstante im Exponenten optimal ist. Diese Konstruktion verwenden wir nun, um zu zeigen, dass viele interessante Entscheidungsprobleme unserer zustandsloser Restartautomaten PSPACE-vollständig sind. Die Idee dieser Konstruktion nutzen wir schließlich, um Reversibilität mit unserem Modell zu nutzen.

Einen weitere interessante Variante stellen schließlich die nicht-deterministischen geordneten Restartautomaten mit Zuständen dar. Dessen Sprachklasse ist recht ungewöhnlich, da sie Sprachen enthält die nicht einmal wachsend kontextsenstiv sind, aber wiederum nicht mal sehr einfache lineare Sprachen. Wir beweisen ein Pumping-Lemma, das es uns erlaubt Leerheit und Endlichkeit zu entscheiden.

Schließlich betrachten wir noch Varianten mit separater Rewrite- und Restartoperation. Während die Automaten mit Nichtdeterminismus und Zuständen alle kontextfreien Sprachen darstellen können, landen wir bei einer Einschränkung, sei es bei den Zuständen oder dem Determinismus, wieder bei den regulären Sprachen. Wir konnten zeigen, dass alle interessanten Entscheidungsprobleme außer natürlich dem Wortproblem, unentscheidbar sind.