Harold V. Mcintosh
Graph theory plays several important roles in the theory of cellular automata, one of which consists in describing the evolution of the automaton, and another of which consists in relating local properties to global properties. Evolution is described by local rules mapping cell neighborhoods into its subsequent state; because successive neighborhoods overlap it is important to be able to take the overlap into account when relating the behavior of successive cells to one another. In illustration, the de Bruijn diagram and its subdiagrams are applied to the study of cellular automata in one dimension.
[html] [ pdf (354 KB)]