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. We improve upon both of these results, by giving a bound of 3ⁿ moves.
Copyright by International Journal of Foundations of Computer Science, World Scientific Publishing Company