The Topological Complexity of MSO+U and Related Automata Models
Szczepan Hummel, Michał Skrzypczak · Fundamenta Informaticae · 2012
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 Bojańczyk to express some asymptotic prop