Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436032 | Theoretical Computer Science | 2014 | 16 Pages |
Abstract
We transform a Muller game with n vertices into a safety game with (n!)3(n!)3 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Daniel Neider, Roman Rabinovich, Martin Zimmermann,