next up previous contents
Next: Up: Periods in time Previous: Overlapping of neighborhoods

The de Bruijn matrix

The basic diagrammatic tool is called a de Bruijn diagram[44,98], whose nodes represent the possible sequences of s symbols chosen from amongst a collection of k; making the convenient choice of integers modulo k for symbols, the nodes become simply s-digit numbers to the base k.

Two nodes are to be linked if the first ends with the same s-1 digit sequence with which the second begins; in other words, if they represent overlapping sequences. Since there is no restriction on the symbols which can be placed at the free ends, each node will have k incoming links and k outgoing links. Having chosen numbers as symbols, the linkage rule is expressible in a simple arithmetic form; namely, that node i is linked to nodes . Since there are nodes in all, the foregoing sums are to be taken modulo S. Indeed the most straightforward representation of a de Bruijn diagram is through the vertices of an S-gon inscribed in a circle, chords marked according to the links present. It can also be represented by a connectivity matrix whose block diagonal structure models this circle.

Since those nodes are linked which differ by shifting their label, dropping the digit on the left and inserting a new digit on the right, de Bruijn diagrams are frequently used in shift register theory. Here, the shift register is simply a moving window which can be used to scan a long chain for the neighborhoods needed by the evolutionary rule of a cellular automaton. Any chain can be reconstructed from the windows by following a path through the diagram, recording the digit associated with each link as one moves along.

Now we need to examine de Bruijn matrices in detail, but to give concrete examples we will stick to low order matrices over the binary alphabet. Let denote the connectivity matrix for a de Bruijn diagram for k symbols and n stages; write for .





next up previous contents
Next: Up: Periods in time Previous: Overlapping of neighborhoods



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx