7 octobre 2013
Pascal Vanier (LACL - UPEC)Les sous-shifts de type fini (SFTs) sont des ensembles de coloriages du plan vérifiant des contraintes locales en nombre fini. Nous allons ici nous intéresser à la conjugaison, la notion d’isomorphisme adaptée aux sous-shifts, et plus particulièrement aux invariants de conjugaison. Alors qu’en dimension 1, l’étude des SFTs est plutôt algébrique, en dimension 2 et plus, elle est liée au calcul. Ceci est dû à la possibilité d’y encoder des diagrammes espace/temps de machines de Turing. Nous allons nous intéresser à la complexité algorithmique de la conjugaison et nous intéresser à deux invariants : l’un classique, le nombre de points périodiques, et l’autre nouveau, l’ensemble de degrés Turing.