Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Hinweis zum Urheberrecht

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-46188
URL: http://geb.uni-giessen.de/geb/volltexte/2007/4618/


Beschreibungskomplexität von Restart-Automaten

Descriptional complexity of restarting automata

Reimann, Jens


pdf-Format: Dokument 1.pdf (743 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Freie Schlagwörter (Deutsch): Beschreibungskomplexität , Restart-Automaten , Zustandskomplexität , Semientscheidbarkeit
Freie Schlagwörter (Englisch): descriptional complexity , restarting automata , state complexity , semi-decidability
CCS - Klassifikation: F.4.2 , F.2.3 , F.1
Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Sprache: Deutsch
Tag der mündlichen Prüfung: 26.01.2007
Erstellungsjahr: 2007
Publikationsdatum: 10.04.2007
Kurzfassung auf Deutsch: 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.
Kurzfassung auf Englisch: 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.