General characteristics.
From this definition three properties of the subset diagram are evident. First, if there is a chain leading from any subset to the empty set, a similar chain will lead from any smaller (included) subset to the empty set. Conversely, if the unit classes lack links to the empty set, no other subset will have such a link either, and there will be no Garden of Eden.
Such will be the case when every node of the de Bruijn diagram has a link associated with each different kind of cell; that is, when it is row stochastic or itself a function. Similarly, the full subset will link with no others, depriving the rule of a Garden of Eden, if every node has an incoming link for each kind of cell; such rules have column stochastic de Bruijn matrices.
Rules for which the Garden of Eden fails to exist for more subtle reasons are much rarer, correspondingly more interesting, and require much more careful scrutiny of the subset diagram for their discovery.
Second, there is a certain residue of the connectivity of the de Bruijn diagram, in the sense that given any source and any destination, there will always be a subset containing the destination accessible from any subset containing the source; but the destination can hold additional nodes.
Third, the subset diagram may not be connected; even if it is, it is interesting to know the largest subsets accessible from a given subset, as well as the smallest. Consider the subsets of largest cardinality accessible from a given unit class
, and another unit class
.
Since there is a chain running from
to a subset containing b and thence onward to a subset even larger than the largest subset accessible from b directly, the resulting contradictions can only be resolved if the cardinalities of all the maximal subsets are the same.
Unfortunately this information alone does not ensure that the subsets encountered along a path are monotonic, not even after a maximal subset has finally been reached.
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx