## Growing Patterns in One Dimensional Cellular Automata

**Bruno Durand****Jacques Mazoyer***Laboratoire de l'Informatique du Parallélisme,**ENS-Lyon, CNRS, 46 Allée d'Italie,**69364 Lyon Cedex 07, France*

#### Abstract

We study limit evolutions of cellular automata (CA) both theoretically and experimentally. We show that either all orbits enter the limit set after less than a finitely bounded number of states, or almost all orbits never enter the limit set. We link this result with a classification of CAs according to their limit behavior due to Culik *et. al.*: in the first case, the considered CA belongs to class 1 while in the second case, it belongs to class 2.

By experiments, we try to measure the convergence speed of orbits to their accumulation points. We compute the maximum number of nested growing segments in a space-time diagram representing a finite portion of an orbit. We observe that, in the average case, this criterion depends only on the CA and not on the configuration. We also observe two kinds of CA with respect to our criterion which correspond to the intuitive notions of chaos and regularity. We do further experiments to explain the fact that the proportion of chaotic diagrams grows with the number of states of the considered CA.