The rows of the period-cycle table can be found from de Bruijn diagrams
in the same way that the cycles can be found from the evolution
diagram; since **2r+1** cells are needed to deduce a generation of
evolution, only about half as many periods as cycles can be worked out
for a given amount of effort. This anomaly is really an artifact of the
way **r** parameterizes the neighborhood, and would disappear if
half-integral increments were taken for **r**.

Similar theoretical conclusions are possible, since the periods are
gotten from a subset of the de Bruijn diagram. A **2r**-stage de Bruijn
diagram for **k** symbols has nodes; **k** times as many links.
Once this number of links has been used up in constructing a path
through the diagram, one of them would have to be repeated. Thus there
is also an exponential upper bound in the rows of the period-cycle
table. For example, if an automaton has a cycle of period 2, it must
already show up in some short ring; if it has not appeared in rings
below a certain limit, it will never appear in longer rings.

Similar statistics can be compiled for the de Bruijn diagrams: the number of periods and their lengths, the number of transients leading into loops, and the corresponding convergence and divergence factors. Failed loops are still interesting; they correspond to strings which are periodic, but which dwindle away with each generation, eventually leaving a residue which is no longer periodic.

Both the cycle diagrams and the period diagrams may have intersecting loops; this simply means that choices are present at certain junctures in working up a chain of cells with a certain property, leading to a greater variety of sequences than would otherwise occur. This choice is particularly vivid in the de Bruijn diagram when one of the loops consists of a single node of identical cells embedded in another loop, since these can be strings of Wolfram's Class IV.

Not only can the de Bruijn diagram can be used to reveal the periodicities of a given cellular automaton, it can also be used in automaton synthesis. That is, desired loops can be marked out first in the diagram, and then a rule chosen which respects the links. For period 1 properties the mapping has to be direct, since each link in the de Bruijn diagram corresponds to a distinct neighborhood in the automaton. Including or excluding it from the period diagram either determines or limits the value of the transition for that neighborhood. For longer periods the evolution corresponds to a composite rule, which may or may not be factorizable in the required manner.

E-mail:mcintosh@servidor.unam.mx