Characterization of -regular languages by first-order formulas

DOI10.1016/0304-3975(83)90027-0zbMATH Open0551.68069OpenAlexW2044335913MaRDI QIDQ800737FDOQ800737

Authors: 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

Recommendations

• Characterization of \(\omega\)-regular languages by monadic second-order formulas
• scientific article; zbMATH DE number 3918353
• First-order definable languages
• Acceptance Conditions for ω-Languages
• Accepting conditions for automata on \(\omega\)-languages

zbMATH Keywords

definabilityfinite automatonco- regular languagesfirst order languageomega language

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Testing and generating infinite sequences by a finite automaton
• Title not available (Why is that?)
• Decision problems forω-automata
• A note on \(\omega\)-regular languages
• Title not available (Why is that?)

Cited In (19)

• A regular characterization of graph languages definable in monadic second-order logic
• Beyond \(\omega BS\)-regular languages: \(\omega T\)-regular expressions and counter-check automata
• Beyond \(\omega \)-regular languages: \(\omega T\)-regular expressions and their automata and logic counterparts
• From LP formulas of the form \(F(t)\) to \(-\omega \)-regular expressions
• Regular languages defined by generalized first-order formulas with a bounded number of bound variables
• Characterization of \(\omega\)-regular languages by monadic second-order formulas
• Infinite-word languages and continuous mappings
• First-order definable languages
• \(X\)-automata on \(\omega\)-words
• A classification of \(\omega\)-regular languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Weak MSO with the unbounding quantifier
• Various hierarchies of \(\omega\)-regular sets
• Title not available (Why is that?)
• \(k\)-counting automata
• On alternating \(\omega\)-automata
• Title not available (Why is that?)
• Title not available (Why is that?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q800737)