1993 | ReviewPaper | Buchkapitel
On syntactic congruences for ω—languages
verfasst von : Oded Maler, Ludwig Staiger
Erschienen in: STACS 93
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
For ω-languages several notions of syntactic congruence were defined. The present paper investigates relationships between the so-called simple (because it is a simple translation from the usual definition in the case of finitary languages) syntactic congruence and its infinitary refinements investigated by Arnold [Ar85]. We show that in both cases not every ω-language having a finite syntactic monoid is regular and we give a characterization of those ω-languages having finite syntactic monoids. As the main result we derive a condition which guarantees that the simple syntactic congruence and Arnold's syntactic congruence coincide and show that all ω-languages in the Borel class Fθ∩Gδ satisfy this condition. Finally we define an alternative canonical object for ω-languages, namely a family of right-congruence relations. Using this object we give a necessary and sufficient condition for a regular ω-language to be accepted by its minimalstate automaton.