Die Berechnungsstärke von Forgetting-Automaten

Abstract

Die sogenannten Forgetting-Automaten wurdeneingeführt, um bestimmte Methoden aus derLinguistik zu modellieren. Formal werden sie alsAutomaten definiert, die eine oder mehrere derOperationen MVL und MVR (Bewegung des Kopfes nachlinks bzw. rechts), DLL und DLR (Löschen desaktuellen Feldes und anschließende Bewegung nachlinks bzw. rechts) sowie ERL und ERR (Ausradierendes aktuellen Feldes mit einem Leerzeichen undanschließende Bewegung nach links bzw. rechts)ausführen können. Da jede (nichtleere) Kombinationdieser sechs Operationen untersucht werden kann,sind insgesamt 63 verschiedene Automatenmodelle zubetrachten.

Wir untersuchen die Berechnungsstärke sowohl imnichtdeterministischen als auch imdeterministischen Fall; dabei vergleichen wir dieverschiedenen Modelle untereinander und mitwohlbekannten Automaten- und Grammatikmodellen ausder Literatur. Weiterhin werden der unäre Fall unddie Abschlusseigenschaften der entstehendenSprachfamilien untersucht.

Forgetting Automata were introduced to modelcertain strategies from linguistics. Formally,they are automata which are able to use one ormore of the operations MVL and MVR (move the headto the left and right, resp.), DLL and DLR (deletethe current field of the tape and move to the leftand right, resp.) as well as ERL and ERR (erasethe current field with the blank symbol and moveto the left and right, resp.). Since any(non-empty) combination of these six operationscan be examined, we have 63 different automatamodels to consider.

We study the computational power in thenondeterministic as well as in the deterministiccase; here we compare the different models offorgetting automata with each other and withwell-known models of automata and grammars.Furthermore the unary case and the closureproperties of the resulting language families areinvestigated.