Dynamics groups of asynchronous cellular automata
Dynamics groups of asynchronous cellular automata
复制标题
异步元胞自动机的动力学群
DOI：
10.1007/s10801-010-0231-y
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
H. Mortveit
中科院分区：
文献类型：
--
作者：
M. Macauley;Jon McCammond;H. Mortveit
我们说一个有限异步元胞自动机（或更一般地说，任何序列动力系统）是π独立的，如果它的周期点集与局部函数的应用顺序无关。在这种情况下，局部函数置换周期点，这些置换生成动力学群。我们之前已经证明了104个可能的细胞自动机规则是π独立的。本文对这类系统的周期态进行了分类，并描述了它们的动力学群，它们是Coxeter群的等价物。动态组提供有关允许动态作为更新序列的函数的信息，因此，以一种新的有趣的方式连接离散动力系统，群论和代数组合学。最后，我们讨论了许多开放的问题和未来的研究方向。
We say that a finite asynchronous cellular automaton (or more generally, any sequential dynamical system) isπ-independent if its set of periodic points are independent of the order that the local functions are applied. In this case, the local functions permute the periodic points, and these permutations generate thedynamics group. We have previously shown that exactly 104 of the possiblecellular automaton rules areπ-independent. In the article, we classify the periodic states of these systems and describe their dynamics groups, which are quotients of Coxeter groups. The dynamics groups provide information about permissible dynamics as a function of update sequence and, as such, connect discrete dynamical systems, group theory, and algebraic combinatorics in a new and interesting way. We conclude with a discussion of numerous open problems and directions for future research.