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

Wednesday, April 03, 2019, 10:30am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10

Speaker: Anton Pirogov


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)


External Links