论文标题
通过编辑距离定义的拓扑空间中的蜂窝自动机和替换
Cellular automata and substitutions in topological spaces defined via edit distances
论文作者
论文摘要
besicovitch伪金属中是在无限序列的一组偏移不变的伪金属中，具有有趣的特性，适合研究细胞自动机的动力学。它们对应于锤距离距离的渐近行为，在更长和更长的前缀上。尽管在文献中已经研究了细胞自动机的动力学，但我们提出了对取代动力学的首次研究。我们将那些产生明确的动力学系统的人表征为统一系统。我们还探索了该伪金属曲线的变体，即Feldman伪金属，其中锤距被Levenshtein距离所取代。就像在Besicovitch空间中一样，蜂窝自动机在这个空间中是Lipschitz，但这里所有替代都均为Lipschitz。在这两个空间中，我们都讨论了这些系统的等效性，并给出了许多示例，并将我们的结果推广到嵌入细胞自动机和取代的莳萝图的类别。
The Besicovitch pseudo-metric is a shift-invariant pseudo-metric on the set of infinite sequences, that enjoys interesting properties and is suitable for studying the dynamics of cellular automata. They correspond 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 pseudo-metric, the Feldman pseudo-metric, 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, and give a number of examples, and generalize our results to the class of the dill maps, that embed both cellular automata and substitutions.
