PLAYING MULLER GAMES IN A HURRY
John Fearnley, Martín Zimmermann · International Journal of Foundations of Computer Science · 2012
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 [Formula: see text] 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 3nmoves.