next up previous contents
Next: The calculus of Up: The Garden of Previous: Ancestorless states for


Regular expressions form an algebraic system in the same way that many other structures, such as groups, semigroups, rings and fields; they probably resemble semigroups more than any of the others. Consequently there are standard aspects of structure theory which may be brought to bear, including the study of equivalence relations, order relations, and mappings which are consistent with the regular operations of sum, concatenation and star. Conway's monograph touches on all these points, without explicitly mentioning them. His theory of ``factors'' is related to the decomposition of an algebraic structure into ideals, with implications for the establishment of a canonical form for regular expressions.

In the case of Garden of Eden configurations, it is noticed that the mere presence of certain strings in a sequence of cells will prevent the whole sequence from having an ancestor; for instance 10101001 is sufficient to block the formation of ancestors for Rule 22. Tracing back from the empty set in the subset diagram, it is seen that all the strings lacking ancestors have to end with 01. A question which can be asked is whether the lack of ancestors is always a local matter, for which definite strings can be assigned responsibility, or whether difficulties can build up more slowly, with the possibility of being reversed before they become inescapable. The presence of loops in the paths leading from the universal set to the empty set allow for a wide variety of ancestorless chains, included among which there is a finite collection of loopless paths, whose maximum length is (exponentially) bounded.

Harold V. McIntosh