Mutations

For the sake of continuity, this posting ought to be considered as an afterthought to the series ``Ancestors,'' to be placed after ``Ancestors (14).'' We really intend the commentary on Wuensche and Lesser's ``Atlas'' to be finished; but there have been some final observations which depend too much on the background already established to be considered separate submissions.

In the process of correcting Z, it is convenient to deflate edge-insensitive neighborhoods. Deflation does not change the lambda ratio, nor the Perron eigenvalues of the de Bruijn diagrams, but it IS essential for getting a probability-based value of Z. In the opposite direction, inflation produces larger neighborhoods, which may be filled by carrying evolution through multiple generations, or which can be used for a finer degree of mutation than that of which the original neighborhood is capable.

Inflation and deflation are special cases of mappings between graphs, special meaning that the mappings are supposed to conserve the linkages and non-linkages within the graph. In turn, inflation and deflation are special cases of a mapping known as duality. At first sight, duality consists of exchanging nodes and links; the nodes of the dual are the links of the original. Dual nodes are joined when the links from the original diagram join consecutively, which is whenever they share a common node.

Duality can be expressed by matrices: invent two new matrices, which will probably be rectangular, and are related to one another by diagonal reflection. For the first matrix, the rows are indexed by nodes, the columns by links. For the second matrix, the reverse is true, rows being indexed by links, and columns by nodes. The elements are zeroes or ones, according to the Boolean predicates tail(node,link) and head(link,node) which express the relation of the node of its argument to the (directed) link which is the other argument.

The rules of matrix multiplication make sense of a sum of the form

as well as a sum of the form

Supposing that a link has exactly one head and one tail, there is just one node for which tail(node,link) is true, so TAIL must be column-stochastic (with just one non-zero element per column); we could call it C for short. Likewise HEAD is row-stochastic because head(link,node) allows just one non-zero element per column; call the matrix R. Therefore the connectivity matrix M for any graph can always be factored by stochastic matrices into the form M=CR (or TAILHEAD).

By definition, the DUAL of M is the graph whose connectivity matrix is RC. Reading this as HEADTAIL, the second equation, above, justifies the use of the name. Moreover, the tautology RCR=RCR, written with parentheses R(CR) = (RC)R, shows the relationship of duality to inflation and deflation, because it shows that the dual can be mapped to the original. Hardly surprising; we associate links with their endpoints. Writing CRC=CRC is also possible.

There could be a second dual , wherein , and so on through an infinite tower. That a matrix is equal to its second dual is not necessarily a theorem, as it is in linear algebra; it's another kind of dual. However, all the de Bruijn diagrams for a given state set constitute exactly such a tower, graded according to the length of the neighborhood.

What is more interesting is whether or not a graph can be a dual, which means giving it the reverse factorization. The conditions are essentially those under which deflation is possible. Of course, a complete de Bruijn diagram can always be deflated; the question is whether the fragments also meet the condition, which has something to do with rows (or columns) being either identical or orthogonal. Details may be found in an article by Hemminger and Beinecke.

One of the applications of inflation is to assure the existence of a new graph, in which all the paths of a certain length taken from an original graph are single links in the new graph. The way to get one is recursively, which is where the dual enters in. To see this, begin with the de Bruijn matrix for (2,1) automata,

0.15em

The product CR is the de Bruijn matrix for (2,3/2) automata:

0.15em

wherein the neighborhoods are of length 4, which are two-step paths of neighborhoods of length 3.

In working with duality it is convenient to note that the product of two C-matrices (column stochastic) is a C-Matrix, that the product of two R-matrices is always an R-matrix, and that the factorization M=CR is always possible. Fragments can be included in a computation, if an epsilon is included amongst the matrix elements, which can take values 0 or 1. Epsilon must always appear in at least one factor, but if desired it can always be placed in the factor on one side exclusively.

Consider the a matrix like , whose elements count the number of paths of length 3. We have

In other words, it is always possible to factorize a product as a single CR combination by invoking a high enough dual. Moreover, we could write

with any epsilons in the middlemost term, thereby relating three-step paths directly to the second dual. This circumstance justifies the assertion that there is always a big enough de Bruijn diagram to inflate a given neighborhood by any desired amount, and that it then includes the paths of matching length.

In the Atlas, inflation is used to obtain finer detail when constructing mutants. Thus, a (2,1) rule is promoted to a (2,2) rule by means of the definition

It could equally well have been promoted to a (2,3/2) rule, a (2,3) rule, or any other; the advantage of skipping (2,3/2) is inflating symmetrically (besides the still finer gradation). As a variant on the theme, had the authors also considered the extension

they could have compared the behavior of second generation ancestors with that of first generation ancestors.

There are two motives for describing duals; one is to show explicitly how the generation of mutants as described in the Atlas fits the matrix and graph theory approach to automata; in particular, the way that Perron eigenvalues are conserved. They are just as much governing parameters as any other which have been introduced, and we have already explored their relation to parameters such as lambda and Z at considerable length. The second motive is to evaluate the direction that hypercomplex algebra might take if the de Bruijn fragments are to be regarded in those terms. Mainly we see that there is already considerable structure present, just from graph theory alone.

The Atlas tends to confirm what has always been suspected --- small changes in the rule of an automaton result in small changes in the evolution itself. It isn't all that easy to quantify such a statement, but the exceptions and anomalies which have been observed along with the regularities might be explained through reference to the diagrams, wherein the opening or closing of loops is a significant event.

There is a whole lore of bounds on the Perron eigenvalue, and also of its separation from the next largest eigenvalue, which has an effect on the rate of convergence of powers of the matrix to equilibrium. By and large, the results are probably not stringent enough to allow predictions about the basins of attraction to be made in the detail shown in the Atlas. However, it might be interesting to do a Monte Carlo simulation of the basins on the basis of the data which we actually do have.

There is an entirely different approach which we have not mentioned at all; the algebra of regular expressions. For example, one might characterize the reversible rules as those for which the regular expression belonging to the A and B fragments must be a sum of starred expressions, none of which contains a sum within a star. That is a concise way of saying that the loops cannot be connected to one another, necessary but not sufficient for reversibility.

In any event, the series really is concluded. A report summarizing the whole commentary is now available on request, as are the two preprints on which it is based. With the help of TeX, many misspellings have been corrected, footnote references added, and formulas beautified. A supplement contains a variety of the smaller de Bruijn diagrams, pair diagrams, and subset diagrams; they may be copied and used as suggested in the commentary.