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: |
Monoid
Discrete mathematics Existential quantification Syntactic monoid Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Computer Science Applications Theoretical Computer Science Decidability Set (abstract data type) Congruence (geometry) Computer Science::Logic in Computer Science Mathematics::Category Theory Free monoid Signal Processing Formal language Information Systems Mathematics |
| 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 |
| Externí odkaz: |
|