Substitutions et automates cellulaires dans des espaces de distance d’édition

Firas Ben Ramdhane
AMU & Université de Sfax, Tunisie
https://www.researchgate.net/profile/Firas-Ben-Ramdhane

Date(s) : 09/11/2021   iCal
11 h 00 min - 12 h 00 min

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.

Catégories



Retour en haut 

Secured By miniOrange