Playing Muller Games in a Hurry

John Fearnley and Martin Zimmermann

This work considers a finite-duration variant of Muller games, and their connection to infinite-duration Muller games. In particular, it studies the question of how long a finite- duration Muller game must be played before the winner of the finite-duration game is guaranteed to be able to win the corresponding infinite-duration game. Previous work by McNaughton has shown that this must occur after Πj₌₁..n(j!1) moves, and the reduction from Muller games to parity games gives a bound of n⋅n!1 moves. We improve upon both of these results, by giving a bound of 3ⁿ moves.

International Journal of Foundations of Computer Science (IJFCS).

(pdf) (bib)