Shift-equivalence of k-ary, one-dimensional cellular automata rules
Ruivo
E
L
P
author
de Oliveira
P
P
B
author
Lobos
F
author
Goles
E
author
2018
English
Cellular automata are locally-defined, 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 time-evolution, 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 shift-equivalence 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 shift-equivalent 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 k-ary, one-dimensional rule. (C) 2018 Elsevier B.V. All rights reserved.
One-dimensional cellular automata
Dynamical behaviour
Dynamical equivalence
Shift equivalence
WOS:000432822500022
exported from refbase (show.php?record=870), last updated on Fri, 27 Jul 2018 11:30:18 -0400
text
files/870_Ruivo_etal2018.pdf
10.1016/j.cnsns.2018.03.017
Ruivo_etal2018
Communications In Nonlinear Science And Numerical Simulation
Commun. Nonlinear Sci. Numer. Simul.
2018
Elsevier Science Bv
continuing
periodical
academic journal
63
280
291
1007-5704