Eilenberg correspondence for Stone recognition
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911030411526144 |
|---|---|
| author | Almeida, Jorge Klíma, Ondřej |
| author_facet | Almeida, Jorge Klíma, Ondřej |
| contents | We develop and explore the idea of recognition of languages (in the general sense of subsets of topological algebras) as preimages of clopen sets under continuous homomorphisms into Stone topological algebras. We obtain an Eilenberg correspondence between varieties of languages and varieties of ordered Stone topological algebras and a Birkhoff/Reiterman-type theorem showing that the latter may me defined by certain pseudo-inequalities. In the case of classical formal languages, of words over a finite alphabet, we also show how this extended framework goes beyond the class of regular languages by working with Stone completions of minimal automata, viewed as unary algebras. This leads to a general method for showing that a language does not belong to a variety of languages, expressed in terms of sequences of pairs of words, which is illustrated when the class consists of all finite intersections of context-free languages. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_00409 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Eilenberg correspondence for Stone recognition Almeida, Jorge Klíma, Ondřej Formal Languages and Automata Theory 46H05 (Primary) 06E15, 08A62 (Secondary) We develop and explore the idea of recognition of languages (in the general sense of subsets of topological algebras) as preimages of clopen sets under continuous homomorphisms into Stone topological algebras. We obtain an Eilenberg correspondence between varieties of languages and varieties of ordered Stone topological algebras and a Birkhoff/Reiterman-type theorem showing that the latter may me defined by certain pseudo-inequalities. In the case of classical formal languages, of words over a finite alphabet, we also show how this extended framework goes beyond the class of regular languages by working with Stone completions of minimal automata, viewed as unary algebras. This leads to a general method for showing that a language does not belong to a variety of languages, expressed in terms of sequences of pairs of words, which is illustrated when the class consists of all finite intersections of context-free languages. |
| title | Eilenberg correspondence for Stone recognition |
| topic | Formal Languages and Automata Theory 46H05 (Primary) 06E15, 08A62 (Secondary) |
| url | https://arxiv.org/abs/2507.00409 |