A HIERARCHICAL-CLASSIFICATION OF CELLULAR AUTOMATA

A central issue in the theory of cellular automata is classification. A classification is a structure imposed on the space of automata which groups together cellular automata with related properties. In this paper a classification based on the action of cellular automata on n-step Markov measures is presented. This classification is hierarchical and parametric. An algorithm is described which efficiently constructs all rules in a given class at a given level of the hierarchy. The utility of the classification is explored in the study of the invariant statistical properties of next-nearest neighbor cellular automata on two states per cell. © 1990.