Uniform multilplicity

Strictly speaking, a de Bruijn diagram describes the sequences which are available in a shift register, one motivation for their study being the regognition of maximum length non-repeating sequences. The Hamiltonian paths which they contain serve that purpose quite nicely. However, it was realized that a variety of link labellings produced useful results in the theory of one dimensional cellular automara.

On the one hand, links can be taken to be neighborhoods. By using the states into which the neighborhoods map as alternative labels, paths through the diagram can be considered to generate the evolution of a configuration. Cellwise, evolution maps several states - the contents of the whole neighborhood - into a single state, but by always taking a neighbor from a fixed location (say the central element, if its length is odd) the mapping can be envisioned as taking place from cell to cell.

Shift-periodic configurations can be identified by Boolean labelling, yes or no (or more formally, true or false), according to whether the desired symmetry is realized. For example, left shift in a three neighbor automaton, given the evolution function $\varphi$, corresponds to the predicate:

$$\equiv \varphi(a,b,c) = c.$$ p_ls(a,b,c) (30)

Any path in the diagram following true labels will create a shifting configuration by simply recording the sequence of neighborhoods. Such labellings can be applied to the evolution generation after generation, while others will have a more limited duration; still, any predicate at all can be introduced to detect some property or other. Another in common use yields counterimages of constant configurations; given state s, take

$$\equiv \phi(a,b,c) = s.$$ p_s(a,b,c) (31)

Thinking that de Bruijn diagrams represent the evolution of automata works in reverse, because by following s sequence of evolved states, one knows the sequence of neighborhoods from which they arose. Finding a given path is equivalent to discovering the ancestor, but it is necessary to look around to find it. Sometimes there is none, when the configuration is part of the Garden of Eden.

The only way to find out whether there are paths of a given description is to make a systematic search. One way to do that is to use a subset diagram.

The idea of subset diagrams has a place in the theory of automata which ought to interest a historian, but suffice it to say that it is a device for conducting searches, creating a covering space for turning non-functions into functions, and much more. There are two subset diagrams, according their derivation from incoming links in the de Bruijn diagram, or outgoing links.

In the development of symbolic dynamics following Hedlund's ideas, Masakazu Nasu [49] showed that there was a homomorphic image of the de Bruijn diagram in the subset diagram, and that under a proper labelling of the states, consisted of an assemblage of trees. It is convenient to call this portion of the subset diagram a Welch diagram. On the other hand, these diagrams are based on the properties of maximal extensions, which were already studied by Hedlund which he attributed to L. R. Welch.