A tutorial on Elementary cellular automata with fully asynchronous updating - General properties and convergence dynamics - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Natural Computing Année : 2020

A tutorial on Elementary cellular automata with fully asynchronous updating - General properties and convergence dynamics

Résumé

We present a picture of the convergence properties of the 256 Elementary Cellular Automata under the fully asynchronous updating , that is, when only one cell is updated at each time step. We regroup here the results which have been presented in different articles and expose a full analysis of the behaviour of finite systems with periodic boundary conditions. Our classification relies on the scaling properties of the average convergence time to a fixed point. We observe that different scaling laws can be found, which fall in one of the following classes: logarithmic, linear, quadratic, exponential and non-converging. The techniques for quantifying this behaviour rely mainly on Markov chain theory and martingales. Most behaviours can be studied analytically but there are still many rules for which obtaining a formal characterisation of their convergence properties is still an open problem.
Fichier principal
Vignette du fichier
tutorial-Fates-AsynchECA-2020-hal-NaCo.pdf (704.25 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02400792 , version 1 (09-12-2019)

Identifiants

Citer

Nazim A. Fatès. A tutorial on Elementary cellular automata with fully asynchronous updating - General properties and convergence dynamics. Natural Computing, 2020, 19 (1), pp.179-197. ⟨10.1007/s11047-020-09782-7⟩. ⟨hal-02400792⟩
148 Consultations
586 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More