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

Eurico L.P. Ruivo, Pedro P.B. de Oliveira, Fabiola Lobos, Eric Goles

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

1 Cita (Scopus)

Resumen

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.

Idioma originalInglés
Páginas (desde-hasta)280-291
Número de páginas12
PublicaciónCommunications in Nonlinear Science and Numerical Simulation
Volumen63
DOI
EstadoPublicada - oct. 2018
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'Shift-equivalence of k-ary, one-dimensional cellular automata rules'. En conjunto forman una huella única.

Citar esto