Minimality and computability of languages of G-shifts
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913890178170880 |
|---|---|
| author | Amir, Djamel Eddine de Menibus, Benjamin Hellouin |
| author_facet | Amir, Djamel Eddine de Menibus, Benjamin Hellouin |
| contents | Motivated by the notion of strong computable type for sets in computable analysis, we define the notion of strong computable type for $G$-shifts, where $G$ is a finitely generated group with decidable word problem. A $G$-shift has strong computable type if one can compute its language from the complement of its language. We obtain a characterization of $G$-shifts with strong computable type in terms of a notion of minimality with respect to properties with a bounded computational complexity. We provide a self-contained direct proof, and also explain how this characterization can be obtained from an existing similar characterization for sets by Amir and Hoyrup, and discuss its connexions with results by Jeandel on closure spaces. We apply this characterization to several classes of shifts that are minimal with respect to specific properties. This provides a unifying approach that not only generalizes many existing results but also has the potential to yield new findings effortlessly. In contrast to the case of sets, we prove that strong computable type for G-shifts is preserved under products. We conclude by discussing some generalizations and future directions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_10610 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimality and computability of languages of G-shifts Amir, Djamel Eddine de Menibus, Benjamin Hellouin Formal Languages and Automata Theory Computational Complexity Discrete Mathematics Dynamical Systems 37B51 37B05 68Q17 F.1.3; G.2 Motivated by the notion of strong computable type for sets in computable analysis, we define the notion of strong computable type for $G$-shifts, where $G$ is a finitely generated group with decidable word problem. A $G$-shift has strong computable type if one can compute its language from the complement of its language. We obtain a characterization of $G$-shifts with strong computable type in terms of a notion of minimality with respect to properties with a bounded computational complexity. We provide a self-contained direct proof, and also explain how this characterization can be obtained from an existing similar characterization for sets by Amir and Hoyrup, and discuss its connexions with results by Jeandel on closure spaces. We apply this characterization to several classes of shifts that are minimal with respect to specific properties. This provides a unifying approach that not only generalizes many existing results but also has the potential to yield new findings effortlessly. In contrast to the case of sets, we prove that strong computable type for G-shifts is preserved under products. We conclude by discussing some generalizations and future directions. |
| title | Minimality and computability of languages of G-shifts |
| topic | Formal Languages and Automata Theory Computational Complexity Discrete Mathematics Dynamical Systems 37B51 37B05 68Q17 F.1.3; G.2 |
| url | https://arxiv.org/abs/2506.10610 |