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

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

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)280-291
Number of pages12
JournalCommunications in Nonlinear Science and Numerical Simulation
Volume63
DOIs
StatePublished - Oct 2018
Externally publishedYes

Keywords

  • Dynamical behaviour
  • Dynamical equivalence
  • One-dimensional cellular automata
  • Shift equivalence

Fingerprint

Dive into the research topics of 'Shift-equivalence of k-ary, one-dimensional cellular automata rules'. Together they form a unique fingerprint.

Cite this