Complex Systems

An Experimental Study of Robustness to Asynchronism for Elementary Cellular Automata Download PDF

Nazim A. Fatès
Electronic mail address: Nazim.Fates@ens-lyon.fr
Laboratoire de l'Informatique du Parallélisme,
ENS Lyon, 46, allée d'Italie,
69 364 Lyon Cedex 07 - France

Michel Morvan
Electronic mail address: Michel.Morvan@ens-lyon.fr
Laboratoire de l'Informatique du Parallélisme and EHESS,
ENS Lyon, 46, allée d'Italie,
69 364 Lyon Cedex 07 - France

Abstract

Cellular automata (CA) are a class of discrete dynamical systems that have been widely used to model complex systems in which the dynamics are specified locally at the scale of the individuals cells. Classically, CA are run on a regular lattice and with perfect synchronicity. However, these two assumptions have little chance of truthfully representing what happens at the microscopic scale for physical, biological, or social systems. One may thus wonder whether CA keep their behavior when submitted to small perturbations of synchronicity.

This work focuses on the study of one-dimensional asynchronous CA with two states and their nearest-neighbors. We define what is meant by "the behavior of CA is robust to asynchronism" using a statistical approach with macroscopic parameters and present an experimental protocol aimed at finding which are the robust one-dimensional elementary CA. To conclude, we examine how the results exposed can be used as a guideline for the research of suitable models according to robustness criteria.