Garden of Eden
To apply the subset diagram to the construction of counterimages, begin with the de Bruijn diagram whose links are the neighborhoods of the automaton. The nodes would be partial neighborhoods whose overlap is attested by the links, and the links can be labelled by the value of the cell which evolves from them. This is a new labelling, different from that obtained from the cell by which the neighborhood is extended. For the latter, all the outgoing nodes have distinct labels, but not for the former unless that is the nature of the rule. Possible ambiguities will be resolved in the subset diagram. Starting from the universal node, following the path dictated by the new configuration, it is possible to obtain all the ancestral configurations.
For example, using Rule 126 and the diagram of the last section, the chain 010 leads
form 
to 
to 
to 
,
the null set. Therefore there is no way that 010 can be part of any evolved configuration.
On the other hand a sequence of 0's leads repeatedly to the subset 
, so there are always counterimages of 
, the quiescent configuration.
Since the universal subset is the starting point, the counterimage might conceivably begin with any pair of states, but since C and D are missing from the repeating subset, there is no ancestor which terminates with either 01 or 10, a mixed pair of states. Such restrictions can prejudice the evolution of finite or cyclical chains of states, yielding additional ancestorless configurations that would not occur for infinite automata.
Moreover, if the infinite automaton is to be ``quiescent at infinity,'' by having only a finite number of excited states, it may turn out that a similar ancestor is impossible.
Altogether, the principal value of the scalar subset diagram is to establish such things as
- the shortest excluded words, the occurrence of any one of which creates a Garden of Eden configuration,
- a maximum length for a minimal excluded word, which is the number of nodes in the portion of the subset diagram connected to the full subset,
- whether exclusion occurs in stages, as key segments are built up.
- a regular expression describing excluded words.
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx