论文标题
十年后的安全玩
Playing Safe, Ten Years Later
论文作者
论文摘要
我们在图表上考虑了两人游戏，并就确保安全目标的策略的记忆大小进行了紧密的界限。更具体地说，我们表明，一项策略的记忆状态数量最少，确保安全目标的最小值是由左列抗抗抗素在语言包容方面的最大抗小节的规模给出的。该结果适用于所有安全目标，而没有任何规律性的假设。我们提供了该一般原则的几个应用。特别是，我们表征了广义可及性游戏中对手的确切内存要求，并且我们证明了与计数器的游戏中存在位置策略。
We consider two-player games over graphs and give tight bounds on the memory size of strategies ensuring safety objectives. More specifically, we show that the minimal number of memory states of a strategy ensuring a safety objective is given by the size of the maximal antichain of left quotients with respect to language inclusion. This result holds for all safety objectives without any regularity assumptions. We give several applications of this general principle. In particular, we characterize the exact memory requirements for the opponent in generalized reachability games, and we prove the existence of positional strategies in games with counters.
