next up previous contents
Next: The subset construction Up: Linear Cellular Automata Previous: The gap theorems

The Garden of Eden

The de Bruijn diagram is particularly useful for the purpose of extending the properties of a neighborhood in a cellular automaton to the properties of chains of cells because they give a particularly graphical way to deal with the overlapping of neighborhoods. Links in the diagram correspond to neighborhoods, nodes to the intervals by which they overlap, and paths through the diagram either to extended neighborhoods or to the sequence of cells into which they evolve.

The de Bruijn diagram differs from the evolutionary diagram in one important respect - it consists wholly of cycles and there are as many links leading into a node as emerging from it; a number which is uniform for each node. Of course this fine balance may be upset when a subdiagram of the de Bruijn diagram is chosen, and one of the important problems may consist in locating the loops which have survived the pruning which created the subdiagram.

Harold V. McIntosh