Minimality and computability of languages of G-shifts
Djamel Eddine Amir
LISN, Saclay
https://members.loria.fr/damir/
Date(s) : 22/04/2025 iCal
11h00 - 12h00
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.
Similarly to the case of sets, we obtain a characterization of G-shifts with strong computable type in terms of a notion of minimality with respect to properties with a low bounded complexity. We show that it can be induced by the result for sets. 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.
This is a joint work with Benjamin Hellouin de Menibus.
Emplacement
I2M Luminy - TPR2, Salle de Séminaire 304-306 (3ème étage)
Catégories
