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

DOI10.1016/0304-3975(86)90024-1zbMath0618.68067OpenAlexW1985984065MaRDI QIDQ1822511

Hideki Yamasaki, Masako Takahashi, Kojiro Kobayashi

Publication date: 1986

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

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

zbMATH Keywords

complexity\(\omega \)-regular languagesmonadic second-order formulastopological hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Related Items (1)

Brzozowski hierarchy of \(\omega\)-languages

Cites Work

• A note on \(\omega\)-regular languages
• Star-free regular sets of ω-sequences
• Decision problems forω-automata
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Characterization of \(\omega\)-regular languages by monadic second-order formulas