Evènement pour le groupe Séminaire Méthodes Formelles

Date 2019-05-28  11:00-12:00
TitreParity, Buchi, Weak 
RésuméThis talk is about the trade-offs between different acceptance conditions for omega-word automata. I will present recent improvements that bring the blow-up up incurred during the translation of alternating parity automata into Buchi (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 Jurdzinski on quasi-polynomially sized Buchi automata that use universal trees to recognise winning strategies in infinite parity games of fixed width. 
OrateurKaroliina Lehtinen 
UrlUniversity of Liverpool 

Aucun document lié à cet événement.

Retour à l'index