细胞自动机中最小邻域与活性值之间的联系

Connections between the minimal neighborhood and the activity value of cellular automata

摘要 Abstract

对于群 $G$ 和有限集合 $A$,细胞自动机是通过有限邻域和局部映射定义在配置空间 $A^G$ 上的变换。尽管邻域不是唯一的,但每个细胞自动机都存在一个唯一的最小邻域,该邻域由影响局部映射行为的所有本质单元组成。细胞自动机的活跃转换是一种模式,当应用局部映射时会改变单元的当前状态。本文研究了细胞自动机的最小邻域与活跃转换数量(即活性值)之间的联系。我们的主要结果表明,活性值通常对局部映射的最小邻域大小施加若干限制。

For a group $G$ and a finite set $A$, a cellular automaton is a transformation of the configuration space $A^G$ defined via a finite neighborhood and a local map. Although neighborhoods are not unique, every CA admits a unique minimal neighborhood, which consists on all the essential cells in $G$ that affect the behavior of the local map. An active transition of a cellular automaton is a pattern that produces a change on the current state of a cell when the local map is applied. In this paper, we study the links between the minimal neighborhood and the number of active transitions, known as the activity value, of cellular automata. Our main results state that the activity value usually imposes several restrictions on the size of the minimal neighborhood of local maps.

细胞自动机中最小邻域与活性值之间的联系 - arXiv