Décidabilité de la conjugaison topologique entre shifts substitutifs de longueur constante

12 octobre 2015

Reem Yassawi

Soit $(X,sigma)$ et $(Y,sigma)$ deux shifts: une conjugaison (topologique) entre ces deux systèmes est un homéomorphisme $Phi:X
ightarrow Y$ qui commute avec le shift. Autrement dit, une conjugaison est un automate cellulaire bijectif entre X et Y. Étant donné deux shifts, nous voudrions savoir s’il existe une conjugaison entre eux. Nous démontrons que si $(X,sigma)$ et $(Y,sigma)$ sont engendrés par des substitutions de longueurs constantes, alors il y a un algorithme qui énumère toutes les conjugaisons entre ces deux systèmes. Ceci est un travail commun avec Ethan Coven et Anthony Quas.