论文标题
在良好的无限字符串上输入驱动的自动机：自动理论和拓扑特性
Input-driven automata on well-nested infinite strings: automata-theoretic and topological properties
论文作者
论文摘要
自1980年代以来，已经研究了在嵌套支架的字符串（称为输入驱动的下降自动机）上操作的自动机，并被显而易见。它们被Alur和Madhusudan扩展到了无限字符串（“明显的下降语言”，Stoc 2004）。本文假设给定的无限字符串始终是良好的，研究了这些自动机的特性。该限制可以从有限字符串上的经典$ω$ - 章程和输入驱动的自动机对相应的$ω$语言进行完整表征。这种表征会导致这些自动机的确定结果，以及在其wadge度上的第一个结果。
Automata operating on strings of nested brackets, known as input-driven pushdown automata, and as visibly pushdown automata, have been studied since the 1980s. They were extended to the case of infinite strings by Alur and Madhusudan ("Visibly pushdown languages", STOC 2004). This paper investigates the properties of these automata under the assumption that a given infinite string is always well-nested. This restriction enables a complete characterization of the corresponding $ω$-languages in terms of classical $ω$-regular languages and input-driven automata on finite strings. This characterization leads to a determinization result for these automata, as well as to the first results on their Wadge degrees.
