Reduction and Learning Techniques for omega-Automata

• Applicant: Privatdozent Dr. Christof Löding
• Subject Area: Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 442233282

The aim of this project is to study reduction and learning techniques for automata on infinite words (omega-automata). One central aspect is the development of algorithms for constructing omega-automata from finite sets of example words. This is a subject that has already been studied intensively for automata finite words but there are almost no results for infinite words. Furthermore, we want to advance the theory of query learning algorithms for omega-automata. Concerning reduction of omega-automata, we are interested in efficient heuristics for reducing the size of deterministic omega-automata (during determinization and directly on given deterministic automata), but we also want to study aspects of exact minimization, which is much more involved than for deterministic automata on finite words.

• DFG Programme: Research Grants