Eilenberg theorems for many-sorted formations
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2016
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909075056361472 |
|---|---|
| author | Vidal, Juan Climent Llópez, Enric Cosme |
| author_facet | Vidal, Juan Climent Llópez, Enric Cosme |
| contents | A theorem of Eilenberg establishes that there exists a bijection between the set of all varieties of regular languages and the set of all varieties of finite monoids. In this article after defining, for a fixed set of sorts $S$ and a fixed $S$-sorted signature $Σ$, the concepts of formation of congruences with respect to $Σ$ and of formation of $Σ$-algebras, we prove that the algebraic lattices of all $Σ$-congruence formations and of all $Σ$-algebra formations are isomorphic, which is an Eilenberg's type theorem. Moreover, under a suitable condition on the free $Σ$-algebras and after defining the concepts of formation of congruences of finite index with respect to $Σ$, of formation of finite $Σ$-algebras, and of formation of regular languages with respect to $Σ$, we prove that the algebraic lattices of all $Σ$-finite index congruence formations, of all $Σ$-finite algebra formations, and of all $Σ$-regular language formations are isomorphic, which is also an Eilenberg's type theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1604_04792 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | Eilenberg theorems for many-sorted formations Vidal, Juan Climent Llópez, Enric Cosme Formal Languages and Automata Theory A theorem of Eilenberg establishes that there exists a bijection between the set of all varieties of regular languages and the set of all varieties of finite monoids. In this article after defining, for a fixed set of sorts $S$ and a fixed $S$-sorted signature $Σ$, the concepts of formation of congruences with respect to $Σ$ and of formation of $Σ$-algebras, we prove that the algebraic lattices of all $Σ$-congruence formations and of all $Σ$-algebra formations are isomorphic, which is an Eilenberg's type theorem. Moreover, under a suitable condition on the free $Σ$-algebras and after defining the concepts of formation of congruences of finite index with respect to $Σ$, of formation of finite $Σ$-algebras, and of formation of regular languages with respect to $Σ$, we prove that the algebraic lattices of all $Σ$-finite index congruence formations, of all $Σ$-finite algebra formations, and of all $Σ$-regular language formations are isomorphic, which is also an Eilenberg's type theorem. |
| title | Eilenberg theorems for many-sorted formations |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/1604.04792 |