Games automata play

Recent Posts

  • December 28, 2017

    Zielonka's algorithm for parity games

    Nathanaël Fijalkow

    This post revisits Zielonka's algorithm.One of the point of this post is to extract from Zielonka's algorithm the notion of signatures, which is the key to the correctness proof for the small progress measure algorithm of Jurdziński.Zielonka'...

  • December 27, 2017

    The backward approach of Muller and Schupp for positional determinacy

    Nathanaël Fijalkow

    This post revisits Muller and Schupp's backward approach to prove the positionality of parity games.The argument is simple and beautiful; credits go to Thomas Colcombet for this presentation.We discussed the technical details of the construction i...

  • December 25, 2017

    Value iteration for parity games

    Nathanaël Fijalkow

    This post presents a generic value iteration algorithm for parity gamesparametrised by universal trees. As special cases this extends the small progress measure of Jurdziński and the succinct progress measure of Jurdziński and Lazić...

  • November 10, 2017

    Separation for parity games

    Nathanaël Fijalkow

    The postulate is that three algorithms for parity games, namely the small progress measure algorithm of Jurdziński, the succinct progress measure algorithm of Jurdziński and Lazić,and the power counting algorithm of Calude et al, ca...