Brzozowski hierarchy of \(\omega\)-languages (Q1095672)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4028935
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Brzozowski hierarchy of \(\omega\)-languages |
scientific article; zbMATH DE number 4028935 |
Statements
Brzozowski hierarchy of \(\omega\)-languages (English)
0 references
1987
0 references
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.
0 references
descriptive power of monadic first-order formulae
0 references
monadic first-order arithmetic
0 references
star-free regular \(\omega \)-languages
0 references
Brzozowski hierarchy of star-free languages
0 references
0.8027797937393188
0 references
0.7940291166305542
0 references
