论文标题
无限持续游戏中色彩内存的状态复杂性
State Complexity of Chromatic Memory in Infinite-Duration Games
论文作者
论文摘要
无限持续游戏领域的一个主要开放问题是表征有限记忆策略确定的获胜条件。通常在边缘色的图上研究无限持续游戏，其获奖条件是根据颜色序列定义的。在本文中，我们研究了一种有限类别的有限内存策略，称为色度有限记忆策略。尽管一般有限内存策略与游戏图的边序一起运行，但色度有限内存策略仅观察到这些边缘的颜色。 该领域的最新结果表明，研究有限内存确定性时，当我们将自己限制在色彩策略上时，更容易说明。另一方面，正如Le Roux（CIE 2020）所表明的那样，一般有限内存策略中的决定性意味着在色度有限内存策略中的决定性。不幸的是，这种结果在状态复杂性方面效率很低：用很少的一般记忆状态替换获胜策略，我们可能需要更多的色度内存状态。本文的目的是找出这种转换的确切状态复杂性。 对于每个获胜条件，对于每个游戏图表，我们都会显示以下内容：如果此游戏图具有带有$ Q $一般内存状态的获胜策略，则它还具有$（q + 1）^n $状态的获胜策略。我们还表明，这种界限几乎很紧。对于每$ q $和$ n $，我们都会构建一个获胜条件和带有$ n + o（1）$节点的游戏图，其中一个人可以以一般内存的$ q $状态获胜，但不能使用$ q^n -1 $ $ $ q^n -1 $ $ $。
A major open problem in the area of infinite-duration games is to characterize winning conditions that are determined in finite-memory strategies. Infinite-duration games are usually studied over edge-colored graphs, with winning conditions that are defined in terms of sequences of colors. In this paper, we investigate a restricted class of finite-memory strategies called chromatic finite-memory strategies. While general finite-memory strategies operate with sequences of edges of a game graph, chromatic finite-memory strategies observe only colors of these edges. Recent results in this area show that studying finite-memory determinacy is more tractable when we restrict ourselves to chromatic strategies. On the other hand, as was shown by Le Roux (CiE 2020), determinacy in general finite-memory strategies implies determinacy in chromatic finite-memory strategies. Unfortunately, this result is quite inefficient in terms of the state complexity: to replace a winning strategy with few states of general memory, we might need much more states of chromatic memory. The goal of the present paper is to find out the exact state complexity of this transformation. For every winning condition and for every game graph with $n$ nodes we show the following: if this game graph has a winning strategy with $q$ states of general memory, then it also has a winning strategy with $(q + 1)^n$ states of chromatic memory. We also show that this bound is almost tight. For every $q$ and $n$, we construct a winning condition and a game graph with $n + O(1)$ nodes, where one can win with $q$ states of general memory, but not with $q^n - 1$ states of chromatic memory.
