Beschreibungskomplexität von Restart-Automaten

Abstract

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. Restarting automata have been studied for approximately 15 years. The use of different computational ressources, combined with restrictions on the process of recognition yields a variety of sub-types of different computational capacity. Our main goal lies in studying the descriptional efficiency of these models. Comparisons are made between different types of restarting automata and towards well-known automaton models and grammars. The results fall in two categories: the first of them is the descriptional complexity of acceptors of regular languages (state complexity) and the second one consists of proofs of non-recursive trade-offs (in descriptional complexity) between more powerful descriptional systems. For the first category, the formal models NFA, DFA, AFA (non-deterministic, deterministic and alternating finite automata) are compared to the two types of restarting automata named R(1) and det-RR(1), respectively. These latter two also characterise the class of regular languages (the proof for det-RR(1)-automata is included here). To obtain results of the second category, several additional proofs concerning (non-)acceptance of valid-computations languages and non-semi-decidable properties are given.