We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A tutorial on elementary cellular automata with fully asynchronous updating: General properties and convergence dynamics.
- Authors
Fatès, Nazim
- Abstract
We present a panorama of the convergence properties of the 256 Elementary Cellular Automata under fully asynchronous updating, that is, when only one cell is updated at each time step. We regroup here various 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.
- Subjects
CELLULAR automata; MARKOV processes; MARTINGALES (Mathematics); DYNAMICAL systems
- Publication
Natural Computing, 2020, Vol 19, Issue 1, p179
- ISSN
1567-7818
- Publication type
Article
- DOI
10.1007/s11047-020-09782-7