Characterizing surjective rules

Some consequences of zero variance are easily described. First and foremost, no path beginning in the subset can ever return, because that would violate the reasoning leading up to Eq. 27. In other words, if two ancestors of a configuration initially coincide --- even for a single partial neighborhood --- and later diverge, they can never recombine. Seen from another point of view, no product of the matrices can ever have a matrix element as large as 2 while the rule has zero variance.

A similar prohibition applies to a pair of isomorphic ancestors; it is only necessary to replace by the set .

It is also necessary that the matrix S corresponding to the subset not have an eigenvalue exceeding that of a de Bruijn matrix, which can be checked in any particular case, but not as easily when it is a general proposition. Essentially, the requirement is that mixed ancestors not proliferate more rapidly than single ancestors as the length of a configuration increases, which would clearly be possible if sections of an ancestor could be freely substituted for one another.

---

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