TY - JOUR

T1 - Shift-equivalence of k-ary, one-dimensional cellular automata rules

AU - Ruivo, Eurico L.P.

AU - de Oliveira, Pedro P.B.

AU - Lobos, Fabiola

AU - Goles, Eric

N1 - Funding Information:
All authors are thankful for a research grant from MackPesquisa – Fundo Mackenzie de Pesquisa. Additionally, P.P.B.O. thanks CNPq, and E.G. and F.L. thank CONICYT.
Publisher Copyright:
© 2018 Elsevier B.V.

PY - 2018/10

Y1 - 2018/10

N2 - 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.

AB - 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.

KW - Dynamical behaviour

KW - Dynamical equivalence

KW - One-dimensional cellular automata

KW - Shift equivalence

UR - http://www.scopus.com/inward/record.url?scp=85044963097&partnerID=8YFLogxK

U2 - 10.1016/j.cnsns.2018.03.017

DO - 10.1016/j.cnsns.2018.03.017

M3 - Article

AN - SCOPUS:85044963097

VL - 63

SP - 280

EP - 291

JO - Communications in Nonlinear Science and Numerical Simulation

JF - Communications in Nonlinear Science and Numerical Simulation

SN - 1007-5704

ER -