Cellular automata and substitutions in the edit-distance space - Ecole Centrale de Marseille Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Cellular automata and substitutions in the edit-distance space

Résumé

The Besicovitch and Weyl pseudo-distances are shift-invariant pseudometrics on the set of infinite sequences, that enjoy interesting properties and are suitable to study the dynamics of cellular automata. They correspond to the asymptotic behavior of the Hamming distance of longer and longer prefixes or factors. In this paper we replace Hamming distance by that of Levenshtein, with the aim of studying symbolic dynamical systems in their associated quotient space. We prove that every cellular automaton is Lipschitz with respect to this new distance, moreover, the shift-map is exactly the identity over those spaces. In addition, we show that, in the Besicovitch and Weyl spaces, substitutions are well-defined essentially only when they are uniform. However, we prove that in the new spaces associated to the Levenshtein distance, all substitutions are well-defined, and furthermore Lipschitz. Finally, we propose a general definitions of pseudo-metrics depending on the distance.
Fichier principal
Vignette du fichier
Article_Automate_cellulaire.pdf (174.57 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03238039 , version 1 (26-05-2021)
hal-03238039 , version 2 (23-06-2021)

Identifiants

  • HAL Id : hal-03238039 , version 2

Citer

Firas Ben Ramdhane. Cellular automata and substitutions in the edit-distance space. Automata 2021, Jul 2021, Marseille, France. ⟨hal-03238039v2⟩
233 Consultations
143 Téléchargements

Partager

Gmail Facebook X LinkedIn More