Influence of the topology of a cellular automaton on its dynamical properties

Notwithstanding the numerous scientific efforts that have been spent to unravel the dynamics of cellular automata (CA), there is still only fragmented and incomplete knowledge of the interference that possibly exists between a CA's dynamical properties in general and its stability in particular, on the one hand, and the whole of its spatial entities and their interconnection, referred to as a CA's topology, on the other hand. Since a clear understanding of this interference is unbearable to fully comprehend the dynamics of CA, this paper is devoted to a quantitative assessment of this interference. More precisely, after pinning down the so-called representative tessellation size (RTS), it is verified to what extent the input sensitivity of 2-state CA and their stability depends on the characteristics of their topology. Therefore, 12 random graphs having six different vertex degree distributions (VDDs) are used to embody the CA's topology and to verify how their dynamics is affected by the specificities of these graphs. It is found that the RTS is 400. Further, the interference is strongest with regard to the CA's stability to the extent that the classification of CA into behavioral classes can be seriously affected by the choice of the VDD. (C) 2012 Elsevier B.V. All rights reserved.