论文标题
较小的进度措施和分离平价游戏的自动机
Smaller Progress Measures and Separating Automata for Parity Games
论文作者
论文摘要
Calude等。最近表明，可以在准多项式时间内解决平价游戏，这是一个具有里程碑意义的结果，导致了许多准分子复杂性的方法。 Jurdinski和Lasic进一步提高了平等游戏的精确复杂性，尤其是当优先级数量较低时（位置数量的对数）。这两种算法都属于现在通常称为“分离自动机：确定性自动机”类别的游戏求解技术，可以用作证人自动机，以确定奇偶校验游戏中的获胜者，最多可达给定数量的状态和颜色。我们建议对Calude等人的方法进行一些调整。这导致了较小的状态空间。这些包括和改进了Fearnley等人早期提出的人。 我们确定了其中两个，共同导致了与Jurdzinski和Lasic的简洁进度措施完全相同的状态空间，这些措施目前将其视为最小的状态空间。因此，剩余的改进，因此导致了状态空间的大小进一步减少，这使我们的方法成为了奇偶校验游戏最简洁的进度措施。
Calude et al. have recently shown that parity games can be solved in quasi-polynomial time, a landmark result that has led to a number of approaches with quasi-polynomial complexity. Jurdinski and Lasic have further improved the precise complexity of parity games, especially when the number of priorities is low (logarithmic in the number of positions). Both of these algorithms belong to a class of game solving techniques now often called separating automata: deterministic automata that can be used as witness automata to decide the winner in parity games up to a given number of states and colours. We suggest a number of adjustments to the approach of Calude et al. that lead to smaller statespaces. These include and improve over those earlier introduced by Fearnley et al. We identify two of them that, together, lead to a statespace of exactly the same size Jurdzinski and Lasic's concise progress measures, which currently hold the crown as smallest statespace. The remaining improvements, hence, lead to a further reduction in the size of the statespace, making our approach the most succinct progress measures available for parity games.
