Skip to Main content Skip to Navigation

Fully asynchronous behavior of double-quiescent elementary cellular automata.

Abstract : In this paper we propose a probabilistic analysis of the fully asynchronous behavior (i.e., two cells are never simultaneously updated, as in a continuous time process) 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) ----> 0 and (1,1,1) ---->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 follows: 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. Among the sixty-four cellular automata belonging to the class we consider, we show that nine of them diverge almost surely on all non-trivial configurations while the fifty-five other converge almost surely to a random fixed point. We show that the exact convergence time of these fifty-five automata can only take the following values: either 0, Θ(nlnn), Θ(n2), Θ(n3), ou Θ(n2n). Furthermore, the global behavior of each of these cellular automata is fully determined by reading its code.
Document type :
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:07:07 AM
Last modification on : Wednesday, November 20, 2019 - 2:52:57 AM


Files produced by the author(s)


  • HAL Id : hal-02101819, version 1



Nazim Fatès, Michel Morvan, Nicolas Schabanel, Eric Thierry. Fully asynchronous behavior of double-quiescent elementary cellular automata.. [Research Report] LIP RR-2005-04, Laboratoire de l'informatique du parallélisme. 2005, 2+20p. ⟨hal-02101819⟩



Record views


Files downloads