Brzozowski hierarchy of \(\omega\)-languages

DOI10.1016/0304-3975(87)90097-1zbMath0632.68079OpenAlexW1978969080MaRDI QIDQ1095672

Masako Takahashi

Publication date: 1987

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90097-1

zbMATH Keywords

Brzozowski hierarchy of star-free languagesdescriptive power of monadic first-order formulaemonadic first-order arithmeticstar-free regular \(\omega \)-languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Cites Work

• Unnamed Item
• Unnamed Item
• First-order logic and star-free sets
• Classifying regular events in symbolic logic
• The dot-depth hierarchy of star-free languages is infinite
• Characterization of \(\omega\)-regular languages by monadic second-order formulas
• Dot-depth of star-free events
• Star-free regular sets of ω-sequences

This page was built for publication: Brzozowski hierarchy of \(\omega\)-languages