Down the borel hierarchy: Solving Muller games via safety games

Neider, D, Rabinovich, R and Zimmermann, M ORCID: 0000-0002-8038-2453 (2012) Down the borel hierarchy: Solving Muller games via safety games .

Text nrz.pdf - Published version Download (167kB) | Preview

Abstract

We transform a Muller game with n vertices into a safety game with (n!)³ vertices whose solution allows 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 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:	Conference Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	15 Jul 2019 12:56
Last Modified:	24 Jan 2026 01:48
DOI:	10.4204/EPTCS.96.13
Related Websites:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3049688
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.