Characterization of \(\omega\)-regular languages by monadic second-order formulas (Q1822511)

Many interesting subclasses of \(\omega\)-regular languages have been characterized in terms of the product topology on \(\Sigma^{\omega}\). We study the relationship between the topological hierarchy of \(\omega\)- regular languages and the complexity of the monadic second-order formulas defining them. Among others, it is proved that open \(\omega\)-regular languages are precisely the \(\omega\)-languages defined by the formulas of the form \(\forall v\exists x\exists P(u,v,x)\), where u and v are \(\omega\)-word variables and x is a number variable. It is also proved that \(\omega\)-regular languages in the class of denumerable unions of closed sets are the \(\omega\)-languages defined by the formulas of the form \(\exists v\exists x\forall yP(u,v,x,y)\).