Paper Info
Title
A tutorial on Elementary cellular automata with fully asynchronous updating -General properties and convergence dynamics
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.
Year
DOI
Venue
2020
10.1007/s11047-020-09782-7
Natural Computing
Keywords
DocType
Volume
Dynamical systems, Asynchronous updating, Convergence, Markov chains
Journal
19
Issue
ISSN
Citations 
1
1567-7818
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Nazim Fatès121225.31