next up previous contents
Next: Subautomata Up: What to look Previous: Periods

Ancestors

Another use of the period diagram is to obtain ancestors of a given chain. The simplest application is to find the ancestors of uniform chains, which follows readily from the fact that each link represents the evolution of the central cell in one neighborhood. All the links evolving into zero determine the chains which must evolve into zero; conversely demanding that given loops evolve into zero determines the rules for which such an evolution is possible. For a binary automaton, that is enough information to determine the rule uniquely.

An interesting exercise is to show that for totalistic automata, the ancestor diagram for constant chains consists of pure loops, without any transients at all. One consequence of this result is that any finite chain which maps into zero can be embedded in a still longer chain which also maps into pure zeroes.

Only slightly more complicated is the determination of the static chains, or still lifes. Rather than choosing neighborhoods which evolve into a constant value, neighborhoods for which the central cell evolves into itself must be chosen. Quite a few other variations on the theme are also possible.

Historically, de Bruijn diagrams were created to solve the problem of finding all the distinct sequences of certain symbols [98]. This idea can be applied to a period diagram, by asking whether all possible sequences of cells can appear as possible evolutions. Since the period diagram is a restriction of the de Bruijn diagram, it may be suspected that they may not; this confirms the existence of ``Garden of Eden'' states for cellular automata. These are chains of cells which can only be seen as initial configurations for an automaton, because they have no ancestors and cannot arise during the course of evolution from any other states.

Searching for a path in a diagram can be a tedious process, but if no more is required than knowing of its existence, Moore's subset diagram [81] provides a way to systematize the search. It is a new diagram, whose nodes are subsets of states; each subset is linked to the union of the states which are linked to its members. Let the evolutionary function, which links nodes in the dew Bruijn diagram, be . Further let A be a subset whose typical member is the node a. Then

defines the linkage between subsets.

One usually starts from the full set, supposing that it does not matter where a path begins, continuing as long as possible. Having arrived at the null subset, it is certain that there was no path of the same characteristics in the original diagram. An even more elaborate subset diagram retaining all details can also be constructed, from which the original paths with all their multiplicities can be extracted.



next up previous contents
Next: Subautomata Up: What to look Previous: Periods



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