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 :
Reports
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101819
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:07:07 AM
Last modification on : Wednesday, May 22, 2019 - 1:32:16 AM

File

RR2005-04.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101819, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

13

Files downloads

23