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.