论文标题
如何为常规目标发挥最佳作用？
How to Play Optimally for Regular Objectives?
论文作者
论文摘要
本文研究了在图形上播放的两人零和游戏的两种游戏，并为以下问题做出了贡献：鉴于目标，为该目标发挥最佳作用需要多少记忆？我们研究常规的目标，其中两个玩家之一的目标是最终播放的颜色顺序属于有限单词的一些常规语言。我们为这两个玩家提供了此类目标的色彩内存需求的不同特征，从中我们得出复杂性理论语句：决定是否存在足够优化的小记忆结构对两个玩家来说都是NP兼容。我们的某些表征结果适用于更一般的目标类别：拓扑封闭和拓扑开放的集合。
This paper studies two-player zero-sum games played on graphs and makes contributions toward the following question: given an objective, how much memory is required to play optimally for that objective? We study regular objectives, where the goal of one of the two players is that eventually the sequence of colors along the play belongs to some regular language of finite words. We obtain different characterizations of the chromatic memory requirements for such objectives for both players, from which we derive complexity-theoretic statements: deciding whether there exist small memory structures sufficient to play optimally is NP-complete for both players. Some of our characterization results apply to a more general class of objectives: topologically closed and topologically open sets.
