论文标题
关于交替均等的简洁性良好的游戏自动机
On the Succinctness of Alternating Parity Good-for-Games Automata
论文作者
论文摘要
我们研究了交替的奇偶校验好游戏（GFG）自动机，即交替的奇偶校验自动机，其中连接性和脱节的选择都可以在线方式解决，而无需了解输入单词的后缀，仍然需要阅读。 我们表明，与非确定性和普遍的对手相比，它们可能更为简洁。此外，我们提出了一个指数确定的过程，并且与识别交替的自动机是否为GFG的问题相结合。我们还研究了决定“半gfgness”的复杂性，这是一种特定于交替自动机的属性，仅需要以在线方式解决非确定性选择。我们表明，这个问题已经是用于在有限单词上交替自动机的pspace-hard。
We study alternating parity good-for-games (GFG) automata, i.e., alternating parity automata where both conjunctive and disjunctive choices can be resolved in an online manner, without knowledge of the suffix of the input word still to be read. We show that they can be exponentially more succinct than both their nondeterministic and universal counterparts. Furthermore, we present a single exponential determinisation procedure and an Exptime upper bound to the problem of recognising whether an alternating automaton is GFG. We also study the complexity of deciding "half-GFGness", a property specific to alternating automata that only requires nondeterministic choices to be resolved in an online manner. We show that this problem is PSpace-hard already for alternating automata on finite words.
