Brzozowski hierarchy of \(\omega\)-languages (Q1095672)

The study of \(\omega\)-languages originated from the decision problem of monadic second-order arithmetic. In this paper the descriptive power of monadic first-order formulae is investigated. It turns out that the ``arithmetic'' hierarchy \(\Sigma_ k\) of \(\omega\)-languages definable in monadic first-order arithmetic forms an infinite hierarchy in and covering the whole class of star-free regular \(\omega\)-languages of \textit{W. Thomas} [Inf. Control 42, 148-156 (1979; Zbl 0411.03031)]. This hierarchy is shown to be closely related to and compatible with premultiplication by sets from the Brzozowski hierarchy of star-free languages.