Project without external funding

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


Project Details
Project duration: 07/200106/2007


Abstract
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.


Principal Investigator


Publications
Go to first page Go to previous page 1 of 5 Go to next page Go to last page

2007
2006
2006
2006
2006
2006
2006
2006
2006
2006

Last updated on 2017-11-07 at 14:51

Share link