一句话:通过刻画识别位置性语言的奇偶自动机,给出 ω-正则语言位置性的判定特征与封闭性结果。
论文研究图上双人博弈中语言的位置性:若以语言 L 为获胜目标时,主角总能只依赖当前位置选择最优策略,则 L 称为位置性的。作者通过刻画识别位置性语言的奇偶自动机,给出了 ω-正则语言位置性的完整特征。由此得到多个推论:位置性可在多项式时间内判定;该性质在有限到无限、单人到双玩家等情形下可提升;前缀无关的位置性目标类对并运算封闭;并在 ω-正则情形下回答了 Kopczyński 的猜想。
In the context of two-player games over graphs, a language L is called positional if, in all games using L as winning objective, the protagonist can play optimally using positional strategies, that is, strategies that do not depend on the history of the play. In this work, we describe the class of parity automata recognising positional languages, providing a characterisation of positionality for ω-regular languages. As corollaries, we establish decidability of positionality in polynomial time, finite-to-infinite and 1-to-2-players lifts, and show the closure under union of prefix-independent positional objectives, answering a conjecture by Kopczyński in the ω-regular case.