Skip to Main content Skip to Navigation
Journal articles

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

Abstract : 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.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-02400792
Contributor : Nazim Fatès <>
Submitted on : Monday, December 9, 2019 - 4:27:31 PM
Last modification on : Friday, February 12, 2021 - 8:07:09 PM
Long-term archiving on: : Tuesday, March 10, 2020 - 9:35:10 PM

File

tutorial-Fates-AsynchECA-2020-...
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

138

Files downloads

307