The Topological Complexity of MSO+U and Related Automata Models
The Topological Complexity of MSO+U and Related Automata Models
复制标题
MSO U 的拓扑复杂性及相关自动机模型
DOI：
--
复制
发表时间：
2012
影响因子：
0.8
通讯作者：
Michal Skrzypczak
中科院分区：
文献类型：
--
作者：
S. Hummel;Michal Skrzypczak
这项工作表明，对于每个I∈ω，存在一个$-Sigma^1_I$-硬ω-字语言，该语言可用一元二阶逻辑定义，并带有去界量词(MSO+U)。这个量词是由Bojanczyk引入的，用来表示一些渐近性质。由于不难看出用ω+U表示的每一种语言都是射影的，我们的发现解决了MSO+U的拓扑复杂性，结果可以立即从Mso-词转移到无限标号树上。作为拓扑难度的结果，我们注意到，没有一个具有Borel接受条件的交替自动机--甚至是具有有界射影复杂性的接受条件--能够捕获所有MSO+U。确定性和非确定性自动机也是如此，因为它们是交替自动机的特例。我们还给出了由Bojanczyk和Colcombet研究的不确定ωB-，ωS-和ωBS-自动机识别的相关语言类的精确拓扑复杂性。此外，我们还证明了对应的交替自动机比非确定自动机具有更高的拓扑复杂性--它们存在于Borel族的所有有限层。这篇论文是[8]的扩展期刊版本。那篇文章的主要定理在这里得到了加强。
This work shows that for each i ∈ ω there exists a $\Sigma ^1_i$-hard ω-word language definable in Monadic Second Order Logic extended with the unbounding quantifier (MSO+U). This quantifier was introduced by Bojanczyk to express some asymptotic properties. Since it is not hard to see that each language expressible in MSO+U is projective, our finding solves the topological complexity of MSO+U. The result can immediately be transferred from ω-words to infinite labelled trees. As a consequence of the topological hardness we note that no alternating automaton with a Borel acceptance condition — or even with an acceptance condition of a bounded projective complexity — can capture all of MSO+U. The same holds for deterministic and nondeterministic automata since they are special cases of alternating ones. We also give exact topological complexities of related classes of languages recognized by nondeterministic ωB-, ωS- and ωBS-automata studied by Bojanczyk and Colcombet. Furthermore, we show that corresponding alternating automata have higher topological complexity than nondeterministic ones — they inhabit all finite levels of the Borel hierarchy. The paper is an extended journal version of [8]. The main theorem of that article is strengthened here.