Whether working with probabilities, measures, or simple evolution, the overlapping which occurs between different neighborhoods comprises the greatest technical obstacle to computations; unless this problem is resolved adequately, further progress is almost impossible. Fortunately, for one dimensional automata, a diagrammatic technique which lies at the heart of shift register theory[31] saves the situation; the diagrams are called de Bruijn diagrams, but they are just simple graphs showing the possible ways in which different neighborhoods can overlap[59]. Erica Jen has shown how many properties of automata can be extracted from such diagrams, especially the static and periodic configurations on a cylinder of fixed circumference[44].
In principle, such a diagram could be extended to automata of higher dimensions, but a problem arises from selecting partial neighborhoods that will join to form full neighborhoods in all directions. The straightforward approach of building up strips of successively higher dimension runs afoul of Post's correspondence principle when arbitrary intermediate strips have to be matched to form the strips of the next higher dimension. If only periodic solutions are required, the problem is still soluble, but again the conflict between large systems and unbounded systems arises, tending to leave the generic properties of aperiodic systems undecidable.
At least in one dimension, there is nothing difficult about a de Bruijn diagram; as applied to cellular automata it is simply a graph in which partial neighborhoods are the nodes, with links connecting those which may overlap to form a full neighborhood. Given this correspondence between links and full neighborhoods, each link is also associated with the evolved cell belonging to the neighborhood. Consequently characteristics of the evolution can be used to select subgraphs of the de Bruijn diagram; for example, there is a subgraph composed of the neighborhoods whose central cell never changes. Global properties of the automaton can be read off in terms of the chains to be found in such a subdiagram; for the present example, the chains determine all the static configurations.
The advantage of using a de Bruijn diagram is that many problems concerning automata are thereby transformed into known problems regarding the tracing of paths through a graph. For instance, no loop can be longer than the total number of nodes in the graph without repeating some segment; but then there must exist still other loops in which the repeated segment is traversed an arbitrary number of times. For example, a binary automaton depending upon nearest neighbors has eight distinct neighborhoods, representable as eight links connecting four nodes, it follows that no static configuration can be more than four cells long without repeating some two-cell partial neighborhood. Thus the static configurations are rather severely constrained.
Sometimes the de Bruijn diagram reveals information about localized aspects of a configuration. For example if an acceptable path terminates at a node in which all the outgoing links are acceptable, it need continue no further. Likewise if all the incoming links are acceptable, the path may begin just as though it had been part of a loop. Thus semi infinite structures may be located, or even finite ones if both ends have such universal terminations. This leads to the phenomenon of membranes and macrocells which Wolfram noticed during the course of his investigations. That is, an automaton may have patches which are isolated from one another by static regions, whose evolutions proceed quite independently.
The converse process is also possible, to define the rule of evolution of an automaton by postulating that the de Bruijn diagram have prescribed properties; for example that the unit cell (0101) must be a static configuration. To the extent that the requirements are not contradictory, and all the possibilities are covered, an automaton may practically be designed to order.
Enumerating the paths through a graph is a classical task, to which many papers have been devoted, but which has a particularly elegant solution in terms of regular expressions. Conway's book on regular algebra[16] expounds the technique; a later article of Backhouse and Carré[4] gives a very thorough presentation.
Probabilistic versions of both the de Bruijn diagrams and the evolutionary diagrams exist, being useful for studying correlations between blocks of cells, or in the numerical calculation of self consistent block probabilities. All the standard theorems regarding positive matrices and stochastic matrices apply. All told, the introduction of graphical techniques to automata studies is very profitable.