Which finite monoids are syntactic monoids of rational ω-languages

Autor: Phan Trung Huy, Do Long Van, Igor Livotsky
Rok vydání: 1992
Předmět:
Zdroj: Information Processing Letters. 42:127-132
ISSN: 0020-0190
Popis: A notion of ω-rigid sets for a finite monoid is introduced. We prove that a finite monoid M is the Arnold's syntactic monoid of some rational ω-language (ω-syntactic for short) if and only if there exists an ω-rigid set for M . This property is shown to be decidable for the finite monoids. Relationship between the family of ω-syntactic monoids and that of ∗-syntactic monoids (i.e. the syntactic monoids of rational languages of finite words) is established.
Databáze: OpenAIRE