Down the Borel hierarchy: Solving Muller games via safety games

Neider, Daniel, Rabinovich, Roman and Zimmermann, Martin (2014) Down the Borel hierarchy: Solving Muller games via safety games THEORETICAL COMPUTER SCIENCE, 560 (P3). pp. 219-234. ISSN 0304-3975, 1879-2294

Text borel.pdf - Author Accepted Manuscript Download (694kB) | Preview

Abstract

We transform a Muller game with n vertices into a safety game with (n!)³ vertices whose solution allows us to determine the winning regions of the Muller game and to compute a finite-state winning strategy for one player. This yields a novel antichain-based memory structure, a compositional solution algorithm, and a natural notion of permissive strategies for Muller games. Moreover, we generalize our construction by presenting a new type of game reduction from infinite games to safety games and show its applicability to several other winning conditions.

Item Type:	Article
Uncontrolled Keywords:	Muller games, Safety games, Permissive strategies, Game reductions
Depositing User:	Symplectic Admin
Date Deposited:	15 Jul 2019 12:55
Last Modified:	23 May 2026 01:41
DOI:	10.1016/j.tcs.2014.01.017
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3050013
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.