Advertisement
Published in:
18-08-2023
Cellular automata and substitutions in topological spaces defined via edit distances
Published in: Natural Computing | Issue 3/2023
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
The Besicovitch pseudometric is a shift-invariant pseudometric over the set of infinite sequences, that enjoys interesting properties and is suitable for studying the dynamics of cellular automata. It corresponds to the asymptotic behavior of the Hamming distance on longer and longer prefixes. Though dynamics of cellular automata were already studied in the literature, we propose the first study of the dynamics of substitutions. We characterize those that yield a well-defined dynamical system as essentially the uniform ones. We also explore a variant of this pseudometric, the Feldman–Katok pseudometric, where the Hamming distance is replaced by the Levenshtein distance. Like in the Besicovitch space, cellular automata are Lipschitz in this space, but here also all substitutions are Lipschitz. In both spaces, we discuss equicontinuity of these systems, give a number of examples, and generalize our results to the class of dill maps, that embeds both cellular automata and substitutions.