Sur les automates cellulaires préservant un sous-shift.

20 janvier 2020

Samuel Petite (LAMFA - Université de Picardie)

Afin d’étudier les propriétés combinatoires des suites infinies, une approche fructueuse consiste à étudier un sous-shift, i.e. un ensemble fermé de suites, invariant par l’action du shift (décalage), associé à ces suites. La théorie des systèmes dynamiques fournit alors des outils pertinents.
Une question classique consiste alors à étudier les symétries de ces systèmes dynamiques, i.e. les auto-conjugaison du système. Dans ce contexte, Morse et Hedlund ont montré que ces auto-conjugaisons correspondent aux automates cellulaires préservant le sous-shift.
Le groupe engendré par ces transformations est toujours dénombrable en général difficile à décrire.
Dans cet exposé, nous présenterons un survol de récentes avancées dans l’étude de ce groupe et notamment ses relations avec la complexité du système symbolique.