Left and right indices

In any event, the maximal class with its links is an image of the de Bruijn diagram, containing all the same paths as the original, but possibly with fewer nodes. The cardinality of the maximal subsets has been called [7] the index of its Rule; strictly the quantity which has been described is a right index, reserving the term left index for the analogous quantity derived from the reversed subset diagram. The handedness evidently refers to the direction in which a configuration would be extended to get a longer configuration.

The two indices need not be equal. For instance, both indices of Rule 6 ( exclusive or) are 1, but for Rule 12 ( right shift) the left index is 1 while the right index is 2.

It is worthwhile understanding the significance of an index and the reason that the two can differ. Fundamentally, the index is the number of different partial neighborhoods which have to be grouped together to reinforce each other if an arbitrarily prescribed configuration is to have an ancestor. For the right shift of Rule 12, extension to the right is pointless if the leftmost cell cannot be arbitrarily chosen, a possibility assured by the index of 2. For left extension the rightmost cell is irrelevant because it will be replaced immediately; any choice will do and the index is 1.

Continuation in either direction from whatever initial cell is always possible for Rule 6, so both its indices are 1. The consequence, however, is that the ancestors resulting from such freedom are all essentially distinct. By contrast, Rule 12 has only one ancestor; the necessary flexibility to construct it must be retained in the set of partial neighborhoods made available at each stage.

---

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx