论文标题
关于交替的良好游戏自动机的简洁性和识别性
On Succinctness and Recognisability of Alternating Good-for-Games Automata
论文作者
论文摘要
我们研究了交替的配对游戏（GFG）自动机，即交替的自动机，其中连接性和脱节性选择都可以在线解决，而无需读取输入单词的后缀，仍将阅读。我们表明，与非确定性和普遍的对手相比，它们可能更为简洁。此外，我们将无确定性gfg自动机的许多结果提高到交替的结果：单个指数确定过程，与GFGNESS问题的上流时间上限，ptime算法，gfgness算法的gfgness问题弱自动机的弱点，以及从$ g_2 $ g_2 $ ptime Aldity a ptime Aldipery a ptime Algiphm a ptime Algrith的降低的算法。 指数。 $ g_2 $的猜想指出，当且仅当一个被称为$ g_2 $游戏的令牌游戏中，第一个玩家赢得了A g_2 $游戏的非确定奇偶校验自动机A是GFG。到目前为止，它仅证明了BüchiAutomata；我们通过证明CobüchiAutomata为其提供进一步的证据。我们还研究了决定“半gfgness”的复杂性，这是一种特定于交替自动机的属性，仅需要以在线方式解决非确定性选择。我们表明，这个问题严格比GFGNESS检查更加困难，GFGNESS检查已经在有限单词上交替进行自动机。
We study alternating good-for-games (GFG) automata, i.e., alternating 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 lift many results from nondeterministic parity GFG automata to alternating ones: a single exponential determinisation procedure, an Exptime upper bound to the GFGness problem, a PTime algorithm for the GFGness problem of weak automata, and a reduction from a positive solution to the $G_2$ conjecture to a PTime algorithm for the GFGness problem of parity automata with a fixed index. The $G_2$ conjecture states that a nondeterministic parity automaton A is GFG if and only if a token game, known as the $G_2$ game, played on A is won by the first player. So far, it had only been proved for Büchi automata; we provide further evidence for it by proving it for coBüchi automata. 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 strictly more difficult than GFGness check, already for alternating automata on finite words.
