Fully asynchronous behavior of double-quiescent elementary cellular automata.

Nazim Fatès (1) , Michel Morvan (1) , Nicolas Schabanel (1) , Eric Thierry (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Cet article présente une analyse du comportement des automates cellulaires élémentaires doublement quiescents (i.e., les deux états sont stables) suivant avec une dynamique totalement asynchrone. Nous montrons que parmi les soixante-quatre règles considérées, neuf d’entre elles divergent presque surement alors que les cinquante-cinq autres convergent presque sûrement. Nous montrons que l’ espérance du temps de convergence de ces règles ne peut prendre que les valeurs suivantes :0, Θ(nlnn), Θ(n2), Θ(n3), ou Θ(n2n). De plus, nous démontrons que le comportement global de l’automate cellulaire en régime totalement asynchrone est entièrement déterminé par la donnée de son code de transition.

Mots clés: Cellular automata; Discrete dynamical systems; Stochastic process

Mots clés: Automates cellulaires; Systèmes dynamiques discrets; Convergence; Processus stochastiques

Domaines: Informatique [cs]

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⟩