Brzozowski hierarchy of -languages
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.
- Characterization of -regular languages by monadic second-order formulas
- Fine hierarchy of regular -languages
- scientific article; zbMATH DE number 3918353
- scientific article; zbMATH DE number 3926262
- The Hausdorff-Kuratowski hierarchy of \(\omega\)-regular languages and a hierarchy of Muller automata
- Characterization of -regular languages by monadic second-order formulas
- Classifying regular events in symbolic logic
- Dot-depth of star-free events
- First-order logic and star-free sets
- scientific article; zbMATH DE number 3237829 (Why is no real title available?)
- scientific article; zbMATH DE number 3366846 (Why is no real title available?)
- Star-free regular sets of ω-sequences
- The dot-depth hierarchy of star-free languages is infinite
- Fine hierarchy of regular \(\omega\)-languages
- Borel hierarchy and omega context free languages.
- Characterization of -regular languages by monadic second-order formulas
- Logic for \(\omega\)-pushdown automata
- Borel ranks and Wadge degrees of context free \omega-languages
- A Hierarchy of Automaticω-Words having a Decidable MSO Theory
- Index sets for ω‐languages
This page was built for publication: Brzozowski hierarchy of \(\omega\)-languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095672)
