De Bruijn diagrams

By a de Bruijn diagram [23] one understands a graph whose nodes are sequences of symbols from some alphabet, for example the set of states of an automaton. The sequences all have the same length, often called the number of stages because of an application to shift register theory [24]; for automata they are partial neighborhoods. In one dimension, a single cell could be dropped from one end or the other of a given neighborhood, although other decompositions are conceivable (dropping or adding two cells, say).

Many authors have used de Bruijn diagrams to study cellular automata, among them Nasu [8], Erica Jen [25], Wentian Li [26], and Wolfram [27]. There does not seem to be any evidence of an attempt to formulate two-dimensional de Bruijn diagrams.

The nodes of a de Bruijn diagram are linked according to their overlap, resulting in a map which reveals the possible succession of contents in a moving window as it advances across an even longer sequence. For automata, the most convenient choice of window size --- the number of stages --- is the length of a full neighborhood, that being the basic unit participating in the evolutionary process.

A de Bruijn diagram is also represented by its connectivity matrix; for this purpose it is convenient to represent the states of a automaton by the digits 0, 1, k-1, its partial neighborhoods by 2r-digit numbers radix k. Multiplication by k shifts cells, arithmetic modulo drops the leftmost cell, adding a single digit number adjoins a new rightmost cell; altogether


As an example, automata have four different partial neighborhoods 00, 01, 10, and 10, overlapping each other to form eight full neighborhoods of three cells each. Regarding these binary strings as numerical indices produces


wherein dots replace zeroes for clarity.

Harold V. McIntosh