The subset matrix
Whether an automaton has a Garden of Eden can be decided at once from its subset diagram, or the algebraic properties of its subset matrix. For most automata the empty set will be accessible from the full set (implying a Garden of Eden), and there will not be that much interest in the remaining structure of the diagram. Contrarily, for an automaton with zero variance and a surjective rule, the very fact that the empty set can be avoided introduces additional structure into the diagram. For example, what are the largest subsets which lead to the empty set? What are the smallest subsets reachable from the full set? What relationships exist between subsets with similar characteristics?
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx