Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
Order Independence In Asynchronous Cellular Automata, Matthew Macauley, Jon Mccammond, Henning S. Mortveit
Order Independence In Asynchronous Cellular Automata, Matthew Macauley, Jon Mccammond, Henning S. Mortveit
Publications
A sequential dynamical system, or SDS, consists of an undirected graph Y, a vertex-indexed list of local functions F_Y, and a permutation pi of the vertex set (or more generally, a word w over the vertex set) that describes the order in which these local functions are to be applied. In this article we investigate the special case where Y is a circular graph with n vertices and all of the local functions are identical. The 256 possible local functions are known as Wolfram rules and the resulting sequential dynamical systems are called finite asynchronous elementary cellular automata, or ACAs, …
Dynamics Groups Of Asynchronous Cellular Automata, Michael Macauley, Jon Mccammond, Henning S. Mortveit
Dynamics Groups Of Asynchronous Cellular Automata, Michael Macauley, Jon Mccammond, Henning S. Mortveit
Publications
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 the dynamics group. We have previously shown that exactly 104 of the possible 223 = 256 cellular 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 …