Moore's subset construction.

The subset construction [28] was devised to solve this precise problem, so that the transcription of Amoroso and Patt's first algorithm [22] into graphical language is readily accomplished.

The subset diagram of a 2r stage k-ary de Bruijn diagram has nodes; if all configurations of this length possess ancestors, then all configurations of whatsoever length will also do so. If some do not, they can be described; in fact there is a regular expression describing every configuration in the Garden of Eden, which is nothing more than the description of the path leading from the full set to the null set in the subset diagram. Frequently required information can be found without having to use the entire subset diagram; the connected component of the full set is often all that is needed.

As an example, consider the connectivity matrix of the subset diagram belonging to the Rule 22. With four partial neighborhoods, the subset diagram has sixteen nodes. Ranking the subsets in order of size places the full subset as number 1 and the empty set as number 16; it is likewise convenient to group intermediate subsets of similar size.

With such an arrangement links between different groups can be discerned, according to variations in the total number of links connecting nodes in the original diagram, which is represented in the subset diagram by the unit classes. Rather than joining to each other, the unit classes will link to the empty set or to larger classes to reflect inhomogenieties in the original linkage.


is the lowest power of with an element linking the full subset to the empty set; one of the Garden of Eden configurations thus revealed is the sequence 10101001.

Note that is partially tridiagonal, in that there are nonzero submatrices only along its principal diagonal, superdiagonal, and subdiagonal. This is not a necessary structure inasmuch as the imbalance between the number of links at the nodes of the de Bruijn diagram could have been more severe than it is, nor is it especially helpful in analyzing this particular matrix.

Nevertheless, the rows corresponding to the unit classes are significant, inasmuch as they suffice to determine all the remaining rows.

Harold V. McIntosh