Unambiguous Automata on Infinite Words

• Applicant: Professor Dr. Thomas Wilke
• Subject Area: Theoretical Computer Science
• Term: from 2013 to 2017
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 233172410

Unambiguous machine and automaton models have been an active area of research in automata theory and formal languages. Results of the applicant and one of his PhD students show that strongly unambiguous omega-automata -- also known as prophetic automata -- are very well suited to classify temporal properties. The objective of the project is to develop a comprehensive theory of unambiguous and strongly unambiguous omega-automata, which, in particular, sheds light on the question in which scenarios unambiguous automata are better suited than deterministic or non-deterministic ones. A specific goal is to apply the theory to be developed to classification problems for omega-languages and logics on infinite words.

• DFG Programme: Research Grants