PLAYING MULLER GAMES IN A HURRY
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 Pi(n)(j=1)(j!+1) moves, and the reduction from Muller games to parity games gives a bound of n center dot n!+1 moves. We improve upon both of these results, by giving a bound of 3(n) moves.
muller games zielonka's algorithm winning strategies