Down the Borel Hierarchy: Solving Muller Games via Safety Games
We transform a Muller game with n vertices into a safety game with (n!)^3 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 per...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2012-10-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1210.2457v1 |
| _version_ | 1818116508847439872 |
|---|---|
| author | Daniel Neider Roman Rabinovich Martin Zimmermann |
| author_facet | Daniel Neider Roman Rabinovich Martin Zimmermann |
| author_sort | Daniel Neider |
| collection | DOAJ |
| description | We transform a Muller game with n vertices into a safety game with (n!)^3 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. |
| first_indexed | 2024-12-11T04:23:38Z |
| format | Article |
| id | doaj.art-73835059ca5a439aafdea9efcf4e10b4 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-11T04:23:38Z |
| publishDate | 2012-10-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-73835059ca5a439aafdea9efcf4e10b42022-12-22T01:21:02ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802012-10-0196Proc. GandALF 201216918210.4204/EPTCS.96.13Down the Borel Hierarchy: Solving Muller Games via Safety GamesDaniel NeiderRoman RabinovichMartin ZimmermannWe transform a Muller game with n vertices into a safety game with (n!)^3 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.http://arxiv.org/pdf/1210.2457v1 |
| spellingShingle | Daniel Neider Roman Rabinovich Martin Zimmermann Down the Borel Hierarchy: Solving Muller Games via Safety Games Electronic Proceedings in Theoretical Computer Science |
| title | Down the Borel Hierarchy: Solving Muller Games via Safety Games |
| title_full | Down the Borel Hierarchy: Solving Muller Games via Safety Games |
| title_fullStr | Down the Borel Hierarchy: Solving Muller Games via Safety Games |
| title_full_unstemmed | Down the Borel Hierarchy: Solving Muller Games via Safety Games |
| title_short | Down the Borel Hierarchy: Solving Muller Games via Safety Games |
| title_sort | down the borel hierarchy solving muller games via safety games |
| url | http://arxiv.org/pdf/1210.2457v1 |
| work_keys_str_mv | AT danielneider downtheborelhierarchysolvingmullergamesviasafetygames AT romanrabinovich downtheborelhierarchysolvingmullergamesviasafetygames AT martinzimmermann downtheborelhierarchysolvingmullergamesviasafetygames |