Diagrams can be represented by connection matrices, through which many properties of the diagram can be deduced more readily than from the diagram itself. There is another representation, in terms of regular expressions, which is often useful. To see how this works, let us try to express the diagram through a set of symbolic equations. Let nodes be represented by capital letters, links by small letters. Then the two-stage de Bruijn diagram for Rule 22 can be written in the form

In such an equation, ``products'' represent concatenation and are usually written without any explicit operator sign, and ``sums'' represent alternative choices and may be read as ``or.'' The symbol represents a null string and acts like a one in products. It is included in the equations to signify that one can get to a node by doing nothing; that is, by following a null link.

A system of equations is ``solved'' in much the same way that a system of algebraic equations would be solved. The distributive law holds, and any variable (the nodes) may be substituted by an equivalent expression. The process of elimination would eventually leave a single variable defined in terms of constants, following which the whole chain of substitutions could be unravelled to obtain the values of all the variables.

There is just one technical point, however, which concerns the procedure to be followed when the same variable occurs on both sides of an equation, as in

An attempt to write

and thence

is very suggestive but hardly justified in a system which lacks any trace of subtraction, division, infinite series, convergence, and the like.

The correct procedure is to set about a series of substitutions

and observe the general form of the result

It is the first term which refuses to disappear; in the context of
arithmetic, multiplication, and a numerical **a** less than 1, it could
be argued that its magnitude eventually becomes arbitrarily small and
hence it can safely be neglected. Here the argument might run along the
lines, that if the symbolic **a** is not the null chain, then
the first term becomes arbitrarily long and can safely be ignored if we
are seeking * finite* solutions to the symbolic equation.

The case is special, because it really doesn't define
anything; any value of **X** whatsoever, including **b**, will work. On the
other hand, if **b** is empty and **a** is not null, the solution must be
empty because otherwise we would be requiring **X** to be equal to
something strictly longer than itself. That, however, is a different
matter.

E-mail:mcintosh@servidor.unam.mx