M.: The topological complexity of MSO+U and related automata models

This work shows that for each i ∈ ω there exists a Σ1i-hard ω-word language definable in Monadic Second Order Logic extended with the un-bounding quantifier (MSO+U). This quantifier was introduced by Bo-jańczyk to express some asymptotic properties. Since it is not hard to see that each language expressible inMSO+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 alter-nating 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 lan-guages recognized by nondeterministic ωB-, ωS- and ωBS-automata stud-ied by Bojańczyk and Colcombet. Furthermore, we show that correspond-ing alternating automata have higher topological complexity than nonde-terministic ones — they inhabit all finite levels of the Borel hierarchy. The paper is an extended journal version of [HST10]. The main theo-rem of that article is strengthened here