Die Berechnungsstärke von Forgetting-Automaten

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.