一句话：刻画了确定性 Büchi 自动机识别且为半位置的目标，并给出多项式时间判定算法。
在图上双人博弈中，位置策略是最简单的一类无需记忆的策略。本文研究由确定性 Büchi 自动机识别的 ω-正则目标中哪些具有半位置性，即无论有限图还是无限图，主角总能使用位置策略最优博弈。作者基于语言理论中的右同余概念，给出了半位置性的三个自然条件，并证明这些条件完整刻画了该类目标。该刻画进一步导出多项式时间算法，可在给定确定性 Büchi 自动机时判定其识别目标是否半位置。结果为无记忆最优策略的可判定性提供了自动机视角的精确边界。
In two-player games on graphs, the simplest possible strategies are those that can be implemented without any memory. These are called positional strategies. In this paper, we characterize objectives recognizable by deterministic B\"uchi automata (a subclass of omega-regular objectives) that are half-positional, that is, for which the protagonist can always play optimally using positional strategies (both over finite and infinite graphs). Our characterization consists of three natural conditions linked to the language-theoretic notion of right congruence. Furthermore, this characterization yields a polynomial-time algorithm to decide half-positionality of an objective recognized by a given deterministic B\"uchi automaton.
@article{paperbot2730,
title = {Half-Positional Objectives Recognized by Deterministic B\"uchi Automata},
author = {Patricia Bouyer and Antonio Casares and Mickael Randour and Pierre Vandenhove},
journal = {Logical Methods in Computer Science},
volume = {Volume 20, Issue 3},
year = {2024},
doi = {10.46298/lmcs-20(3:19)2024}
}