Date: Thu, 11 Apr 1996 22:42:51
To: ca@think.com
It is nearly time to take up with the new books, but it may be worth a final look at a few more background articles. The role of Shifts of Finite Type and Sofic Systems in cellular automata theory is still not entirely clear, mainly because they seem to have arisen from other interests.
In the process of topologizing symbol sequences, continuous functions distinguish certain subshifts, namely those which can be the images of the full shift; On the one hand this characterizes cellular automata as having the continuous functions for their rules of evolution, while on the other, subshifts which exclude a countable list of words show up as the resultant images under continuous maps.
There is already a relationship between language theory and cellular automata, wherein languages define the admissible sequences so that their transformation by the evolution of the cellular automaton can be studied; some recent articles are devoted to this exact issue. For whatever reasons, students of differential equation theory, among others, decided to use sequences defined by paths in a certain kind of graph whose connectivity matrix defines the exclusions. Having found that the resulting class was not closed under homomorphism, they decided to close it by introducing sofic systems; essentially beginning with the dual of the matrix from which subshifts of finite type were taken.
Naturally it is a temptation to study possible relationships between subshifts, especially automorphisms and endomprphisms, just as Hedlund did for the full shift. The results do not seem to be quite as conclusive, there being numerous articles devoted to the subject and its variant. The most comprehensive seems to be
R. F. Williams,
"Classification of subshifts of finite type,"
Annals of Mathematics 98 120-153 (1973),
with Errata ibid 99 380-381 (1974).
which depends upon the previous
R. F. Williams,
"Classification of one-dimensional attractors,"
in: Global Analysis,
Proceedings of Symposia in Pure Mathematics, volume 14
American Mathematical Society, Providence, Rhode Island
pages 341-361 (1970),
which in turn harks back to the still earlier
R. F. Williams,
One-dimensional non-wandering sets
Topology 6 473-487 (1967).
All three articles contain an abundance of category-theory diagrams. Much of that is caused by relating one-sided shifts to two sided shifts, and more is due to situating the derivations in the abstract realm of mappings between topological partitions. Basically, the idea is that equivalences between shifts should correspond to equivalences between their defining matrices. One complication is that the matrices have positive integer elements, possibly just zeroes and ones, and they are rarely symmetric. Thus the Jordan form may be non-trivial, and the equivalences ought to be expressed by the same class of matrix. Even avoiding inverses by making A equivalent to B via the mapping R by demanding AR = RB, there are questions of algebraic propriety.
The principal determinant of the equivalence between subshifts seems to be their entropy, which can be defined topologically, measure theoretically, or algebraically, as the (logarithm of the) largest, or Perron eigenvalue of the matrix from which they derive. Unfortunately, that alone does not suffice; more of the Jordan canonical form being needed, with restrictions caused by the admissible matrix elements.
The final items on the list of Nasu's publications in Part (4) also contain discussions of mappings between Shifts of Finite Type, as well as between Sofic Systems.
For our immediate purposes, the interesting information to be derived from
these articles is their reliance on an old property which one learns while
studying linear algebra or numerical analysis, but then forgets for lack of
an apparent application. The usual definition of equivalence between matrices
A and B is that some matrix U satisfies the equation 
, commonly
exhibited when B is a diagonal matrix. Something of the sort still works when
A and B are square matrices of different dimensionalities; for rectangular U
it is still possible that U B = A U with the discrepancy in dimensions being
absorbed by zero eigenvalues and associated eigenvectors.
It is also possible that neither matrix is supposed to be diagonal, in which case there could be matrices reducing each to diagonal forms (Lambda) and (Mu), respectively. Then it could be said that A = U V, whilst B = V U, wherein U and V are variants on the diagonalizers (essentially multiplied by another diagonal matrix). So there is a kind of equivalence relation, which Williams calls strong equivalence, wherein two matrices are equivalent if they arise from the product of two (usually noncomuting) factors, or from a chain of such factorizations. From this it iseasy to get R and S for which R A = B R and B S = S B.
On the other hand, a little algebraic manipulation provides matrices U and V
and an arbitrary function f for which 
and 
;
often f is simply a power, yielding Williams' weak equivalence. Unravelling
its chain of factors shows that strong equivalence implies weak equivalence;
it is moreover what turns up in the numerical LR method of diagonalizing
matrices, so it is not such a strange concept.
One of Williams' great concerns was whether it worked the other way around, so that once the powers behaved, a chain of factorizations could be discovered. Given that the factorization which defines a matrix and its dual would lead to a nicely intuitive dual tower, it would be nice to characterize equivelent shifts-of-finite-type as those connected by a chain of duality.
Anyway, it is useless to attempt a homomorphism between two shifts if their matrices do not have at least one eigenvalue in common; moreover for reasons having to do with positivity, at least one of the pairs had better be the largest, Perron, eigenvalue.
Working with automata which are known to be reversible, just as with those without Garden of Eden, there is ample opportunity to factor the matrices in the de Bruijn diagram, because of the property in each fragment that there are just as many links as nodes. Of course, the links may be numbered any way that one wishes, leading to an ambiguity according to the permutation group for the links. This is something to be borne in mind for the later discussion.
This review of symbolic dynamics has been undertaken for the bearing it might have for the description of the two new books; it is essentially material which we have just recently studied in detail, in spite of having known about it for several years. Offline correspondence with David Hillman was instrumental in calling our attention to the significance of Williams' series of papers. At the same time, the improved versatility of nxlcau as we learn better how to use its graphics facilities has allowed checking such things as the relation of Welch's indices to the subset and pair diagrams. Mainly we can now save on paper what could only be watched on the screen in the DOS version.
The approach to these questions which we have previously used has already been explained in detail during the course of the review of Wuensche and Lesser's "Atlas" so there does not seem to be much reason to go over it again, except as it may be needed in discussing specific details. That viewpoint worked directly from the trinity of graphs, using tensor powers of the de Bruijn fragments to deduce properties of the automaton.