论文标题
确定性BüchiAutomata认可的半定位目标
Half-Positional Objectives Recognized by Deterministic Büchi Automata
论文作者
论文摘要
在图表上的两人游戏中，最简单的策略是可以在没有任何内存的情况下实现的策略。这些称为位置策略。在本文中，我们表征了通过确定性的Büchi自动机（Omega-regardar Absporives的子类）识别的目标，即半定位的目标，也就是说，主角可以始终使用位置策略（超过有限的和无限图）来最佳地发挥作用。我们的特征包括与正确一致性的语言理论概念有关的三种自然条件。此外，这种表征产生了多项式时间算法，以确定给定的确定性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üchi 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üchi automaton.
