PLAYING MULLER GAMES IN A HURRY

Fearnley, John and Zimmermann, Martin ORCID: 0000-0002-8038-2453 (2012) PLAYING MULLER GAMES IN A HURRY. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 23 (3). pp. 649-668.

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

Official URL: http://dx.doi.org/10.1142/s0129054112400321

Abstract

<jats:p>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 3<jats:sup>n</jats:sup>moves.</jats:p>

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:	19 Jan 2023 00:37
DOI:	10.1142/S0129054112400321
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3050015