next up previous
Next: Definition Up: Linear Cellular Automata via Previous: Complementary graph

The de Bruijn diagram

It is nearly impossible to do any work with linear cellular automata without encountering the fact that their neighborhoods overlap, so that it is preferable to begin with this circumstance as a fundamental fact. Shift register theory is a discipline based on the treatment of overlapping sequences, so it is not surprising that its fundamental tool, the de Bruijn diagram, would be useful for automata theory.

Although this diagram is explained in Solomon Golomb's fundamental book [7] on shift registers, it actually has a venerable history which has been traced by Anthony Ralston in an article in the American Mathematical Monthly [8].





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