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.
0.3em
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
E-mail:mcintosh@servidor.unam.mx