Discrete Mathematics & Theoretical Computer Science (Jan 2007)
Asynchronous Cellular Automata and Brownian Motion
Abstract
This paper deals with some very simple interacting particle systems, \emphelementary cellular automata, in the fully asynchronous dynamics: at each time step, a cell is randomly picked, and updated. When the initial configuration is simple, we describe the asymptotic behavior of the random walks performed by the borders of the black/white regions. Following a classification introduced by Fatès \emphet al., we show that four kinds of asymptotic behavior arise, two of them being related to Brownian motion.
Keywords