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.
Origine : Fichiers produits par l'(les) auteur(s)