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

DOI10.1016/0304-3975(83)90027-0zbMath0551.68069OpenAlexW2044335913MaRDI QIDQ800737

Kojiro Kobayashi, Masako Takahashi, Hideki Yamasaki

Publication date: 1984

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

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90027-0

zbMATH Keywords

finite automatondefinabilityfirst order languageco- regular languagesomega language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Interpolation, preservation, definability (03C40) Basic properties of first-order languages and structures (03C07)

Related Items (4)

Infinite-word languages and continuous mappings ⋮ A regular characterization of graph languages definable in monadic second-order logic ⋮ \(X\)-automata on \(\omega\)-words ⋮ Various hierarchies of \(\omega\)-regular sets

Cites Work

• A note on \(\omega\)-regular languages
• Decision problems forω-automata
• Testing and generating infinite sequences by a finite automaton
• Unnamed Item
• Unnamed Item
• Unnamed Item

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