Ruivo, E. L. P., de Oliveira, P. P. B., Lobos, F., & Goles, E. (2018). Shiftequivalence of kary, onedimensional cellular automata rules. Commun. Nonlinear Sci. Numer. Simul., 63, 280–291.
Abstract: Cellular automata are locallydefined, synchronous, homogeneous, fully discrete dynamical systems. In spite of their typically simple local behaviour, many are capable of showing complex emergent behaviour. When looking at their timeevolution, one may be interested in studying their qualitative dynamical behaviour. One way to group rules that display the same qualitative behaviour is by defining symmetries that map rules to others, the simplest way being by means of permutations in the set of state variables and reflections in their neighbourhood definitions, therefore defining equivalence classes. Here, we introduce the notion of shiftequivalence as another kind of symmetry, now relative to the concept of translation. After defining the notion and showing it indeed defines an equivalence relation, we extend the usual characterisation of dynamical equivalence and use it to partition some specific binary cellular automata rule spaces. Finally, we give a characterisation of the class of shiftequivalent rules in terms of the local transition functions of the cellular automata in the class, by providing an algorithm to compute the members of the class, for any kary, onedimensional rule. (C) 2018 Elsevier B.V. All rights reserved.
