PLAYING MULLER GAMES IN A HURRY

Fearnley, John and Zimmermann, Martin (2012) PLAYING MULLER GAMES IN A HURRY INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 23 (3). pp. 649-668. ISSN 0129-0541, 1793-6373

Text ws-ijfcs.pdf - Author Accepted Manuscript Download (434kB) | Preview

Abstract

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 = <inf>1</inf> 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. © 2012 World Scientific Publishing Company.

Item Type:	Article
Uncontrolled Keywords:	Muller games, Zielonka's algorithm, winning strategies
Depositing User:	Symplectic Admin
Date Deposited:	15 Jul 2019 13:09
Last Modified:	23 May 2026 01:41
DOI:	10.1142/S0129054112400321
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3050015
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.