DMTCS Proceedings, 2007 Conference on Analysis of Algorithms, AofA 07

Font Size:  Small  Medium  Large

Asynchronous Cellular Automata and Brownian Motion

Philippe Chassaing, Lucas Gerin


This paper deals with some very simple interacting particle systems, elementary 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 et al., we show that four kinds of asymptotic behavior arise, two of them being related to Brownian motion.

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional