General menu

Each state has its own ancestor matrix; products of several ancestor matrices describe the ancestors of sequences of cells. Consequently, the ancestor menu makes provision for a matrix accumulator which holds the matrix counting the ancestors of all the cells which have been entered, running from left to right. Thus, for a binary automaton, a places the ancestor matrix for state 0 in the accumulator; b does the same for state 1. If there are more states, additional letters are used to generate their matrices.

Corresponding capital letters multiply the accumulator by the appropriate matrix. Thus aAABBA would leave a matrix in the accumulator telling how many ancestors the sequence 000110 had, classified according to the states in the margins. Summing all the elements of the matrix gives the total number of ancestors, the trace tells the number of ancestors in a ring of the given circumference, while the element tells how many are embedded in a field of zeroes.

A very limited amount of matrix arithmetic is provided; for example = saves the accumulator and x recovers it. The operator X multiplies the accumulator by the saved matrix; Q squares the accumulator. The latter is useful for obtaining high powers quickly.

The second moment of the ancestor distribution yields the distribution's variance, so the option t is included to calculate the sum of the tensor squares of the individual de Bruijn matrices. Since its high powers and their traces are of interest (the power corresponds to the length of the chain whose ancestor is being sought), the operator T squares the matrix which it encounters in the tensor square position (the first matrix of the sequence must be introduced by the operator t).

Ultimately the largest eigenvalue dominates the powers of all these matrices, which are positive matrices to which the analysis of Frobenius and Perron applies. The options l (de Bruijn matrix in the accumulator) and L (tensor square) estimate these eigenvalues through successive squaring, reporting the result in a little panel of their own.



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx