Projekt ohne Drittmittelfinanzierung

Restart-Automaten: Varianten, Abschlusseigenschaften und Komplexität von Entscheidungsproblemen


Details zum Projekt
Projektlaufzeit: 07/200106/2007


Zusammenfassung
Die "Restart-Automaten" sind ein theoretisches Modell für die in der
Linguistik verwendete "Analyse durch Reduktion",
bei der Sätze analysiert werden,
indem sie durch das wiederholte Ersetzen von Satzteilen
vereinfacht werden.
Dabei wird dieser Ersetzungsprozess solange iteriert,
bis entweder ein Fehler entdeckt wird, oder bis ein
korrekter elementarer Satz erreicht wird.
Durch die verschiedenen Varianten der Restart-Automaten,
wie deterministisch oder nicht-deterministisch,
monoton oder nicht-monoton, etc.
ergibt sich eine ganze Hierarchie von Sprachklassen,
wobei die kontext-freien Sprachen,
die deterministischen kontext-freien Sprachen
und die Church-Rosser Sprachen
als spezielle Klassen auftreten.
Im Rahmen dieses Projekts soll der Einfluss weiterer syntaktischer
Faktoren
auf die Ausdruckskraft der verschiedenen Varianten der Restart-Automaten
untersucht werden.
Eine zentrale Frage ist dabei die nach dem Bezug der sich
jeweils ergebenden Sprachklasse zu den wachsend kontext-sensitiven Sprachen
auf der einen Seite und zu den allgemeinen kontext-sensitiven Sprachen
auf der anderen Seite.
Ferner interessiert insbesondere, inwieweit die Trennung
der eigentlichen Reduktionsschritte von den Restart-Schritten
die Ausdruckskraft dieser Automaten erhöht.


Projektleitung


Weitere Projektbeteiligte


Publikationen
Go to first page Go to previous page 1 von 5 Go to next page Go to last page

2007
2006
2006
2006
2006
2006
2006
2006
2006
2006

Zuletzt aktualisiert 2017-11-07 um 14:51