Asynchronous behavior of double-quiescent elementary cellular automata

Submitted to STACS 2005In this paper we propose a probabilistic analysis of the asynchronous behavior of elementary finite cellular automata (i.e. ${0,1}$ states, radius 1 and unidimensional) for which both states are quiescent (i.e. $(0,0,0) \mapsto 0$ and $(1,1,1) \mapsto 1$). It has been experimentally shown in previous works that introducing asynchronism in the global function of a cellular automata was perturbing its behavior, but as far as we know, only few theoretical work exists on the subject. The cellular automata we consider live on a ring of size $n$ and asynchronism is introduced as follow: at each time step one cell is selected uniformly at random and the transition is made on this cell while the others stay in the same state. Under these conditions, we prove that the considered cellular automata can be classified relatively to their expected convergence time: Among the sixty-four cellular automata belonging to the class we consider, we show that nine of them diverge on all non-trivial configurations while the fifty five other always converge to a fixed point. We then study the convergence time of these fifty five automata and show that it can only take the following values: either $0$, $\Theta(n \ln n)$, $\Theta(n^2)$, $\Theta(n^3)$, or $\Omega(n2^n)$. More than that, we prove that the global behavior of any of these cellular automata is fully determined by reading its code. We end the paper by showing how some of these results can be extended to another kind of asynchronism in which at each time step, each cell has independently the same fixed probability to make its transition