An atlas of limit set dynamics for asynchronous elementary cellular automata

作者：Macauley M; Mortveit H S^*

来源：Theoretical Computer Science, 2013, 504: 26-37.

DOI：10.1016/j.tcs.2012.09.015

• Cellular automata
• Periodic points
• Sequential
• Update sequence
• ECA
• pi-independence
• Cycle-equivalence
• Atlas

In this paper we provide an overview of the possible omega-limit set structures for 104 of the 256 asynchronous elementary cellular automata over the circle graph on n vertices. We consider only fixed, sequential updates where the update sequence is given by a permutation of the vertices, that is, the class of sequential dynamical systems. The ECA rules covered are precisely the pi-invariant rules, that is, the rules for which the set of periodic points does not depend on the permutation update sequence. This paper reviews existing work on pi--invariance and cycle-equivalence, and provides and atlas of the possible limit set structures up to topological conjugation.

• 出版日期2013-9-16
• 单位Virginia Tech; 美国弗吉尼亚理工大学(Virginia Tech)