Die Berechnungsstärke von Forgetting-Automaten

Auf dem Gebiet der Automatentheorie (einem Teilgebiet der theoretischen Informatik) werden abstrakte Maschinen als theoretische Modelle für Computer und für Berechnungen im Allgemeinen betrachtet. Die Automatentheorie und die Theorie der formalen Sprachen haben viele Anwendungen - unter anderem in der Linguistik. Neben den grundlegenden Grammatiktypen des Linguisten Noam Chomsky wurden in den vergangenen Jahrzehnten weitere Modelle erforderlich, um Konzepte aus der Linguistik zu formalisieren und linguistische Fragestellungen zu lösen. Beim Modell des Forgetting-Automaten wird versucht, die syntaktische Korrektheit einer Eingabe durch schrittweise Verkürzung bzw. Vereinfachung zu überprüfen. In dieser Arbeit wird der Forgetting-Automat ausführlich beschrieben und formal definiert. Nach der Zusammenstellung der aus der Literatur bereits bekannten Ergebnisse werden in drei Kapiteln die Berechnungsmächtigkeit für den allgemeinen und für den unären Fall eines Eingabealphabets sowie die Abschlusseigenschaften der definierten Sprachfamilien eingehend untersucht.