|   | 
Details
   web
Record
Author Ruivo, E.L.P.; de Oliveira, P.P.B.; Lobos, F.; Goles, E.
Title Shift-equivalence of k-ary, one-dimensional cellular automata rules Type
Year 2018 Publication Communications In Nonlinear Science And Numerical Simulation Abbreviated Journal Commun. Nonlinear Sci. Numer. Simul.
Volume 63 Issue Pages 280-291
Keywords One-dimensional cellular automata; Dynamical behaviour; Dynamical equivalence; Shift equivalence
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. (C) 2018 Elsevier B.V. All rights reserved.
Address [Ruivo, Eurico L. P.; de Oliveira, Pedro P. B.] Univ Presbiteriana Mackenzie, Fac Comp & Informat, Rua Consolacao 896, BR-01302907 Sao Paulo, SP, Brazil, Email: eurico.ruivo@mackenzie.br
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language (up) English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1007-5704 ISBN Medium
Area Expedition Conference
Notes WOS:000432822500022 Approved
Call Number UAI @ eduardo.moreno @ Serial 870
Permanent link to this record