论文标题
配对$ω$ -PUSHDOWN AUTOMATA
Good-for-games $ω$-Pushdown Automata
论文作者
论文摘要
我们介绍了GOD-GAMES $ω$ -PUSHDOWN AUTOMATA（$ω$ -GFG-PDA）。这些是自动机，其非确定性可以根据到目前为止处理的输入来解决。 GOD-GAMENEMES使自动机由游戏，树木和其他自动机组成，这些应用程序否则需要确定性自动机。我们的主要结果是，$ω$ -GFG-PDA比确定性$ω$ - 俯卧撑自动机更具表现力，并且以$ω$ -GFG-PDA指定的获胜条件的无限游戏解决了无限的游戏。因此，我们已经确定了一个新的$ω$ -Contextfree获胜条件，该条件可确定解决游戏。因此，$ω$ -GFG-PDA的普遍性问题也在exptime中。此外，我们研究了$ω$ -GFG- PDA认可的一类语言的封闭属性，以及$ω$ -PUSHDOWN AUTOMAMATA和语言的商品的可决定性。最后，我们将$ω$ -GFG-PDA与$ω$ - 可视化的PDA进行比较，研究以$ω$ -GFG-PDA解决非确定性所需的资源，并证明$ω$ -GFGGGG-PDA的奇偶校验指数层次结构是Infinite。 这是本文Arxiv的校正版本：2001.04392V6最初于2022年1月7日发布。
We introduce good-for-games $ω$-pushdown automata ($ω$-GFG-PDA). These are automata whose nondeterminism can be resolved based on the input processed so far. Good-for-gameness enables automata to be composed with games, trees, and other automata, applications which otherwise require deterministic automata. Our main results are that $ω$-GFG-PDA are more expressive than deterministic $ω$- pushdown automata and that solving infinite games with winning conditions specified by $ω$-GFG-PDA is EXPTIME-complete. Thus, we have identified a new class of $ω$-contextfree winning conditions for which solving games is decidable. It follows that the universality problem for $ω$-GFG-PDA is in EXPTIME as well. Moreover, we study closure properties of the class of languages recognized by $ω$-GFG- PDA and decidability of good-for-gameness of $ω$-pushdown automata and languages. Finally, we compare $ω$-GFG-PDA to $ω$-visibly PDA, study the resources necessary to resolve the nondeterminism in $ω$-GFG-PDA, and prove that the parity index hierarchy for $ω$-GFG-PDA is infinite. This is a corrected version of the paper arXiv:2001.04392v6 published originally on January 7, 2022.
