Substitutions et automates cellulaires dans des espaces de distance d’édition
Firas Ben Ramdhane
I2M, Aix-Marseille Université
Date(s) : 15/03/2022 iCal
17h00 - 18h00
La dynamique symbolique se concentre en général sur la topologie de Cantor, pour laquelle le décalage est un système chaotique. Pour la pseudo-métrique de Besicovitch (qui correspond à une limite normalisée de la distance de Hamming entre des préfixes de plus en plus grands), le décalage est en revanche une isométrie. Il a été démontré également que les automates cellulaires sont bien définis dans l’espace où l’on quotiente par les suites à pseudométrique 0 (appelé espace de Besicovitch). Nous montrons que dans cet espace, la fonction induite par une substitution est bien définie si et seulement si elle est constante ou la substitution est uniforme.
D’autre part, en remplaçant la distance de Hamming par la distance de Levenshtein (qui correspond au nombre minimal d’opérations d’édition pour trouver un mot à partir d’un autre), on obtient une autre pseudo-métrique qui commute avec le décalage, induit une topologie moins fine que celle de Besicovitch, et un espace quotient dans lequel les automates cellulaires et toutes les substitutions sont bien définis. Ces résultats s’étendent aux « dill maps », qui sont des objets généralisant les automates cellulaires et les substitutions.
Finalement, nous nous intéressons à des propriétés dynamiques. Nous montrons que les substitutions uniformes induisent des systèmes équicontinus sur les deux espaces, et nous terminons par des exemples de substitutions et automates cellulaires témoignant de la différence entre les deux espaces.
Le séminaire des doctorant⋅es de l’I2M et du CPT à Luminy regroupe chaque semaine les doctorant⋅es du site autour d’un exposé plus ou moins (in)formel, dans un cadre convivial. Il est évidemment ouvert aux étudiant⋅es de master et aux doctorant⋅es d’autres laboratoires.
C’est au rez-de-chaussée du bâtiment de « l’ancienne BU », dans la salle « Séminaire 2 » (au fond à gauche en sortant de l’escalier si vous venez de l’étage, au fond à droite si vous entrez par le rez-de-chaussée). Attention : l’entrée dans le labo nécessite un badge. En cas de souci (de type : être bloqué⋅e dehors), appeler le 04 91 26 95 91.
Emplacement
I2M Luminy - Ancienne BU, Salle Séminaire2 (RdC)
Catégories
