Loading…
Report
Minimality and computability of languages of G-shifts
Amir, Djamel Eddine, de Menibus, Benjamin Hellouin
Saved in:
| Title | Minimality and computability of languages of G-shifts |
|---|---|
| Authors | Amir, Djamel Eddine, de Menibus, Benjamin Hellouin |
| Publication Year |
2025
|
| Description |
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.
Comment: Accepted to ICALP 2025 |
| Document Type |
Working Paper
|
| Subject Terms |
