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-65264
URL: http://geb.uni-giessen.de/geb/volltexte/2008/6526/


Die Berechnungsstärke von Forgetting-Automaten

Glöckler, Jens


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

Bookmark bei Connotea Bookmark bei del.icio.us
Freie Schlagwörter (Deutsch): Theoretische Informatik , Automatentheorie , Formale Sprachen , Forgetting-Automaten
Freie Schlagwörter (Englisch): theoretical computer science , automata theory , formal languages , forgetting automata
MSC - Klassifikation: 68Q45
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: 05.09.2008
Erstellungsjahr: 2008
Publikationsdatum: 20.10.2008
Kurzfassung auf Deutsch: Die sogenannten Forgetting-Automaten wurden
eingeführt, um bestimmte Methoden aus der
Linguistik zu modellieren. Formal werden sie als
Automaten definiert, die eine oder mehrere der
Operationen MVL und MVR (Bewegung des Kopfes nach
links bzw. rechts), DLL und DLR (Löschen des
aktuellen Feldes und anschließende Bewegung nach
links bzw. rechts) sowie ERL und ERR (Ausradieren
des aktuellen Feldes mit einem Leerzeichen und
anschließende Bewegung nach links bzw. rechts)
ausführen können. Da jede (nichtleere) Kombination
dieser sechs Operationen untersucht werden kann,
sind insgesamt 63 verschiedene Automatenmodelle zu
betrachten.



Wir untersuchen die Berechnungsstärke sowohl im
nichtdeterministischen als auch im
deterministischen Fall; dabei vergleichen wir die
verschiedenen Modelle untereinander und mit
wohlbekannten Automaten- und Grammatikmodellen aus
der Literatur. Weiterhin werden der unäre Fall und
die Abschlusseigenschaften der entstehenden
Sprachfamilien untersucht.
Kurzfassung auf Englisch: Forgetting Automata were introduced to model
certain strategies from linguistics. Formally,
they are automata which are able to use one or
more of the operations MVL and MVR (move the head
to the left and right, resp.), DLL and DLR (delete
the current field of the tape and move to the left
and right, resp.) as well as ERL and ERR (erase
the current field with the blank symbol and move
to the left and right, resp.). Since any
(non-empty) combination of these six operations
can be examined, we have 63 different automata
models to consider.



We study the computational power in the
nondeterministic as well as in the deterministic
case; here we compare the different models of
forgetting automata with each other and with
well-known models of automata and grammars.
Furthermore the unary case and the closure
properties of the resulting language families are
investigated.