The pair diagram


Whether a configuration has multiple ancestors can be resolved with the subset diagram, but an alternative, the pair diagram, is easier to interpret. The nodes of a pair diagram are pairs of nodes from the original diagram; labelled links join pairs whenever both members of the pair are joined by links with that same label. Paths in the pair diagram correspond to pairs of paths in the original diagram; they do not even have to originate at the same node. However, the same path taken twice can always be found amongst any others, so that the original diagram is always embedded in the pair diagram.

The pertinent question is whether there are any other, and how many, paths besides. The pair diagram is the appropriate arena for the second of Amoroso and Patt's constructions [22]. One might also refer to Tom Head's recent proposal [29].

The pair diagram for the Rule 22 automaton is subordinate to the maximal matrix which would correspond to Rule 0 or Rule 255, the location of the remainder of whose elements is shown by 's in the following matrix:


The diagram just described pertains to ordered pairs; a variant which is frequently encountered is the unordered diagram in which the distinction between and is considered insignificant. A smaller diagram results; it can be gotten by coalescing the nodes of the larger diagram.

Harold V. McIntosh