论文标题
可及性游戏和平价游戏
Reachability Games and Parity Games
论文作者
论文摘要
平价游戏是定位确定的。这是一个基本和古典的结果。在2010年，Calude等人。在有限的平等游戏中显示出突破性的结果：可以在准多项式时间内计算获胜地区及其位置获胜策略。 在本文中，我们为这两个结果提供了独立且详细的证明。本文的结果并不是原始的。他在1998年发表的Zielonka的想法可能出现了无限平等游戏的位置决定性结果。为了显示准多项式时间，我们遵循Lehtinen的注册游戏，她在2018年介绍了该游戏。尽管Lehtinen's Algorithm的Algorithm的时代复杂性并不是最佳的，这是最佳的，这是很简单的，并且在他们的概念上是有趣的。我们的各种证明是原始证明的新或简化。本文中的主题也包括针对可及性游戏的最佳吸引力的定义和计算。
Parity games are positionally determined. This is a fundamental and classical result. In 2010, Calude et al. showed a breakthrough result for finite parity games: the winning regions and their positional winning strategies can be computed in quasi-polynomial time. In the present paper we give a self-contained and detailed proofs for both results. The results in this paper are not meant to be original. The positional determinacy result is shown for possibly infinite parity games using the ideas of Zielonka which he published in 1998. In order to show quasi-polynomial time, we follow Lehtinen's register games, which she introduced in 2018. Although the time complexity of Lehtinen's algorithm is not optimal, register games are conceptually simple and interesting in their own right. Various of our proofs are either new or simplifications of the original proofs. The topics in this paper include the definition and the computation of optimal attractors for reachability games, too.
