If is the number of ancestors of x, we have
because the 2 r cells at which the ancestors of x overlap the ancestors of y when x and y are joined must coincide. Moreover, there can be no ancestor of xy which does not begin with an ancestor of x, nor which does not terminate with an ancestor of y.
The overlapping of neighborhoods which must be taken into account in calculating ancestors can be summarized very concisely by the relation
when a is a letter and x is a word (or the reverse). If both are words a similar relation holds, but the merged product was not defined with quite the generality required to restrict the overlap involved.
Since the determination of the ancestors of a given word plays an important role in all aspects of the calculation of evolutions, it is fortunate that the subset diagram used to locate excluded words can be generalized slightly to a form which will provide both the number of counterimages of a word and the counterimages themselves.
The subset diagram was derived from the 2r-stage de Bruijn diagram whose links were labelled for the neighborhoods of a automaton because the links also correspond to the cells that evolve from the neighborhoods which the links represent. Thus following out a path according to the evolved cells automatically yields the ancestor involved; the subset construction was invoked because of a need to obtain all the possible paths, and moreover to obtain them systematically.
Links were the only information recorded in the subset diagram because interest in the diagram was limited to knowing which combinations, or subsets, of nodes could be linked to get a given evolution. However, if each node is assigned a -ple (quadruple for a automaton), the exact linkage of neighborhoods could be shown, not just the mere indication that such a linkage exists.
If we use Rule 126 as an example, we need the table of transitions
In other words all neighborhoods evolve into ones with the exception of 111 and the quiescent neighborhood 000.
The de Bruijn diagram for this rule is
while the vector subset diagram will have the form
The shortest excluded word for this rule is 010; generally any sequence ending in 010 is excluded. To determine the subset to which a quadruple leads we have only to determine its non- components. To obtain the number of ancestors for any sequence, say 1101, we begin with the quadruple (1,1,1,1), and apply the formula within the quadruple belonging to each digit in turn. Finally we sum the components.
Thus we conclude that there are 4 ancestors of 1101 according to Rule 126. If we wanted the actual ancestors, we should have performed the arithmetic symbolically, as shown in the last column of the table.