Parity, Büchi, Weak

21^st February 2019, 13:00
Karoliina Lehtinen

Abstract

This talk is about the trade-offs between different acceptance conditions for omega-word automata.

I present recent improvements that bring the blow-up up incurred during the translation of alternating parity automata into Büchi and weak automata into line with the current algorithms solving parity games. I will finish by discussing the gap between the upper and lower bounds for this problem, and what it tells us about where to go next.

The technical part of this talk is based on currently unpublished work with Laure Daviaud and Marcin Jurdzi?ski on quasi-polynomially sized Büchi automata that use universal trees to recognise winning strategies in infinite parity games of fixed width.