!Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (email@example.com), CBLU, University of Leeds >
If this point of view is adopted, then we have three rules of inference.
The notation stands for the continued alternative and is read ``a star.'' Any symbolic expression constructed by the aid of concatenation, alternative selection, and the star operation, is called a regular expression. Regular expressions are ideally suited to describing paths through a diagram. and conversely, any regular expression has a diagrammatic representation. Conway's monograph is a concise reference for regular expressions and their properties.
If we apply these principles to the de Bruijn diagram for Rule 22 above, we find the following chain of substitutions
Finally we have
of which the leading term is significant and the remainder represent transients.
Although we have set up the equations for the evolution of one generation of a automaton for the special case of Rule 22, in fact the equations have the same form for all rules. Given the general evolution table
the equations are, in symbolic form,
with the general solution
For symmetric rules we would have b= h and e = g. If 0 were a quiescent state, we would have a = 0.
For infinite or cyclic chains the interesting part of these solutions would be the starred right hand expression common to the four nodes. In essence the remainder of the expression tells how to get to the designated node from any other, while the main term tells how to keep returning to that node. For purposes of reference we could tabulate the results for all the symmetric, quiescent rules for automata. These are just Wolfram's ``legal'' rules.
Table: Paths through the de Bruijn diagrams of Wolfram's ``legal'' Rules.