Journal
NATURAL COMPUTING
Volume 19, Issue 1, Pages 179-197Publisher
SPRINGER
DOI: 10.1007/s11047-020-09782-7
Keywords
Dynamical systems; Asynchronous updating; Convergence; Markov chains
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available