next up previous
Next: Symbolic de Bruijn Up: Reversible Cellular Automata Previous: The pair diagram

Vector subset diagram

The subset diagram is concerned with the existence of paths in the original diagram, whatever their point of origin, which it discovers by trying them all. However, it records them in terms of ``at least one path,'' displayed according to the collection of nodes which could serve as an origin (row index) versus the collection of possible destinations (column index). The principal information revealed by the subset diagram is: what amount of choice in selecting a terminal right neighborhood remains, having prescribed both the leftmost partial neighborhood and that a configuration has evolved in a certain way? To the degree that none remains, the configuration cannot have had an ancestor.

Paths leading to the empty set reveal this information; other paths or loops indicate variations in the possible partial neighborhoods to be found at any stage in constructing ancestors. Indeed, Moore's original intention was locating paths leading to the unit classes --- paths capable of isolating one single node from the original diagram, thus casting an automaton into a known state.

In a more accurate reckoning, when counting the paths becomes of interest, specific endpoints are required, and the dichotomy between ``some'' or ``none'' is no longer appropriate. One way to retain this additional information is to enlarge the nodes in the subset diagram, making each a ``vector'' whose components are the original nodes; matrices linking vector nodes preserve the original links. However, we should also consider splitting the original de Bruijn matrix into k parts, just because we are interested in the differences in what can be linked with one symbol in contrast to what can be linked with another; each part is assigned to its own subset.

For a formal definition of the entire vector subset diagram, define instead a connectivity matrix. Suppose that is a projection matrix whose elements are zero save for those diagonal elements for which the partial neighborhood belongs to S. In particular, the projector for the full set is the unit matrix, for the empty set, the zero matrix.

Then, using the matrix D of Eq. 7, the element of the vector subset matrix indexed by subsets S and T is just

All these references to vectors and matrices can be avoided by establishing a suitable linkage within the cartesian product of the subset diagram with the original diagram, although they reappear when the connectivity matrix of the composite diagram is formed. For Rule 22 (or any other rule) the result would be a matrix with submatrices.

In any event, multiplying vector subset matrices induces a product of submatrices, from which most of the information which one desires can already be extracted. They may as well be used directly, discarding the intermediary of the vector subset matrix.



next up previous
Next: Symbolic de Bruijn Up: Reversible Cellular Automata Previous: The pair diagram



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