Skip to main content
Log in

Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations

Natural Computing Aims and scope Submit manuscript

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 \le 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 \(({\texttt{0011}})^*\) induction patterns.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. it turns out that this point is important to prove the max-sensitivity of some rules.

References

  • Aracena J, Demongeot J, Fanchon E, Montalva M (2013) On the number of update digraphs and its relation with the feedback arc sets and tournaments. Discrete Appl Math 161(10):1345–1355

    Article  MathSciNet  MATH  Google Scholar 

  • Aracena J, Fanchon E, Montalva M, Noual M (2011) Combinatorics on update digraphs in boolean networks. Discrete Appl Math 159(6):401–409

    Article  MathSciNet  MATH  Google Scholar 

  • Aracena J, Goles E, Moreira A, Salinas L (2009) On the robustness of update schedules in boolean networks. Biosystems 97:1–8

    Article  Google Scholar 

  • Cook M (2004) Universality in elementary cellular automata. Complex Syst 15(1):1–40

    MathSciNet  MATH  Google Scholar 

  • de Oliveira PPB (2014) On density determination with cellular automata: results, constructions and directions. J Cell Autom 9(5–6):357–385

    MathSciNet  MATH  Google Scholar 

  • Fatès N (2011) Stochastic cellular automata solve the density classification problem with an arbitrary precision. In: STACS’2011, vol 9 of Leibniz international proceedings in informatics (LIPIcs), pp 284–295

  • Fatès N (2014) A guided tour of asynchronous cellular automata. J Cell Automata 9(5–6):387–416

    MathSciNet  MATH  Google Scholar 

  • Gardner M (1970) Mathematical games: the fantastic combinations of John Conway’s new solitaire game “Life”. Sci Am 223(4):120–123

    Article  Google Scholar 

  • Kari J (2005) Theory of cellular automata: a survey. Theor Comput Sci 334(1–3):3–33

    Article  MathSciNet  MATH  Google Scholar 

  • Montalva M, Perrot K, de Oliveira PPB, Ruivo E (2017) Sensitivity to synchronism in some boolean automata networks. In: AUTOMATA 2017 exploratory papers proceedings, pp 69–76

  • Montalva M, Perrot K, de Oliveira PPB, Ruivo E (2018) Characterisation of the elementary cellular automata in terms of their maximum sensitivity to all possible asynchronous updates. Chaos Solitons Fractals 113:209–220

    Article  MathSciNet  MATH  Google Scholar 

  • Noual M (2012) Mises à jour de réseaux d’automates. Ph.D. thesis, Ecole normale supérieure de lyon, Laboratoire de l’Informatique du Parallélisme

  • Wolfram S (2002) A new kind of science. Wolfram Media

Download references

Acknowledgements

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.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Kévin Perrot.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Perrot, K., Montalva-Medel, M., de Oliveira, P.P.B. et al. Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations. Nat Comput 19, 51–90 (2020). https://doi.org/10.1007/s11047-019-09743-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11047-019-09743-9

Keywords

Navigation