|   | 
Details
   web
Record
Author Perrot, K.; Montalva-Medel, M.; de Oliveira, P.P.B.; Ruivo, E.L.P.
Title Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations Type
Year 2020 Publication Natural Computing Abbreviated Journal Nat. Comput.
Volume 19 Issue 1 Pages 51-90
Keywords Synchronism sensitivity; Elementary cellular automata; Update digraph
Abstract This work is a thoughtful extension of the ideas sketched in Montalva et al. (AUTOMATA 2017 exploratory papers proceedings, 2017), aiming at classifying elementary cellular automata (ECA) according to their maximal one-step sensitivity to changes in the schedule of cells update. It provides a complete classification of the ECA rule space for all period sizes n[ 9 and, together with the classification for all period sizes n <= 9 presented in Montalva et al. (Chaos Solitons Fractals 113:209-220, 2018), closes this problem and opens further questionings. Most of the 256 ECA rule's sensitivity is proved or disproved to be maximum thanks to an automatic application of basic methods. We formalize meticulous case disjunctions that lead to the results, and patch failing cases for some rules with simple arguments. This gives new insights on the dynamics of ECA rules depending on the proof method employed, as for the last rules 45 and 105 requiring o0011THORN induction patterns.
Address [Perrot, Kevin] Univ, Aix Marseille Univ.,Toulon,CNRS,UMR 7020, Marseille, France, Email: kevin.perrot@lis-lab.fr
Corporate Author Thesis
Publisher Springer Place of Publication Editor (up)
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1567-7818 ISBN Medium
Area Expedition Conference
Notes WOS:000517129300006 Approved
Call Number UAI @ eduardo.moreno @ Serial 1162
Permanent link to this record