TY - JOUR
T1 - Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations
AU - Perrot, Kévin
AU - Montalva-Medel, Marco
AU - de Oliveira, Pedro P.B.
AU - Ruivo, Eurico L.P.
N1 - Funding Information:
This work was partially supported by FONDECYT Iniciación 11150827; CNPq; ECOS-CONICYT C16E01; PACA project FRI-2015 01134; PEPS JCJC INS2I project CGETA; Young Researcher project ANR-18-CE40-0002-01 “FANs”; STIC-AmSud CoDANet project: 19-STIC-03 Campus France 43478PD and CAPES 88881.197456/2018-01; CAPES PrInt project 88887.310281/2018-00; and MackPesquisa Edital 2018.
Publisher Copyright:
© 2019, Springer Nature B.V.
PY - 2020/3/1
Y1 - 2020/3/1
N2 - 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 (0011) ∗ induction patterns.
AB - 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 (0011) ∗ induction patterns.
KW - Elementary cellular automata
KW - Synchronism sensitivity
KW - Update digraph
UR - http://www.scopus.com/inward/record.url?scp=85068932668&partnerID=8YFLogxK
U2 - 10.1007/s11047-019-09743-9
DO - 10.1007/s11047-019-09743-9
M3 - Article
AN - SCOPUS:85068932668
SN - 1567-7818
VL - 19
SP - 51
EP - 90
JO - Natural Computing
JF - Natural Computing
IS - 1
ER -