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

• Antragsteller: Professor Dr. Friedrich Otto
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2002 bis 2006
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5379894

Im Rahmen des Projekts soll der Einfluss verschiedener 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.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Polen, Tschechische Republik
• Beteiligte Personen: Professor Dr. Krzysztof Lorys; Dr. Frantisek Mraz; Dr. Martin Platek