文章基本信息

标题：Down the Borel Hierarchy: Solving Muller Games via Safety Games
本地全文：下载
作者：Daniel Neider ; Roman Rabinovich ; Martin Zimmermann 等
期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2012
卷号：96
页码：169-182
DOI：10.4204/EPTCS.96.13
出版社：Open Publishing Association
摘要：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.