Restarting automata: Variants, closure properties and complexity of decision problems

• Applicant: Professor Dr. Friedrich Otto
• Subject Area: Theoretical Computer Science
• Term: from 2002 to 2006
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants
• International Connection: Czech Republic, Poland
• Participating Persons: Professor Dr. Krzysztof Lorys; Dr. Frantisek Mraz; Dr. Martin Platek