Bi-Weekly Talk: Anton Pirogov: A unified approach to Büchi determinization

Mittwoch, 03.04.2019, 10.30 Uhr

Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, Erweiterungsgebäude E3, Raum 9u10

Vortragender: Anton Pirogov

 

Titel: A unified approach to Büchi determinization

 

Nondeterministic Büchi automata are one of the simplest types of finite automata on infinite words and are successfully applied in model checking and synthesis. In some settings nondeterminism is not feasible in practice, but determinization of Büchi automata is a difficult problem with a long history and multiple different solutions. In our work we noticed similarities between two different determinization constructions, namely the construction of Safra and the construction of Muller and Schupp. We studied these similarities to obtain a generalized algorithm, from which both constructions can be recovered as special cases. In this talk I will sketch both constructions, illuminate their relationship, give an idea of our unified procedure and discuss some of its advantages. (Joint work with Christof Löding)