new books and old articles (16)
We have come up to chapter 5 in a review of the new book by Douglas Lind and Brian Marcus, "An Introduction to Symbolic Dynamics and Coding" recently published by Cambridge University Press. Although not dedicated to cellular automata, most of its content is thoroughly relevant, with direct applications to automata theory.
Taking the viewpoint that the de Bruijn diagram is the fundamental structure for cellular automata, we find that Chapter 5 is not so much concerned with how paths through the diagram describe the evolution of configurations, as how different descriptions can be given to the same path. In essence, that is coding theory (sometimes caled transducer theory), the title of Chapter 5.
This is the chapter where the authors expound their "state-splitting" theory, whose role is sufficiently important that one of its diagrams occupies a place of honor on the cover of the book. Basically the problem is that although Symbolic Dynamics works with sequences, the best representation of sequences seem to be paths through a diagram. But the question is: "What diagram?" No one diagram fits all requirements, bringing on the study of equivalence and interchangeability between graphs.
Supposing that it is possible to reduce the study of sequences and mappings between sequences to the study of diagrams (directed graphs, to be precise), problems have only been transferred to another arena; the only justification for the substitution would have to be that it is a more familiar arena. But diagrams are well described by their connectivity matrices, so the arena is linear algebra, albeit over the integers or rationals, and in any event with respect to positive matrices.
The discussion of the Perron-Frobenius theory in the earlier chapters results from this agenda, but there is more to come. Although that theory encompasses individual matrices, their eigenvectors, eigenvalues, and canonical forms, there remain questions of factorization, equivalence, transformation and membership in families. Subsequent chapters get to deal with such annoyances. For the moment, Chapter 5 gives procedures which can be used to relate two sequences to one another, and conditions under which success can be expected.
Chapter 6 introduces some of the rudiments of point set topology, then goes on to topologize dynamical systems and discuss the importance of topological relationships. Important among these are the invariants, which typically include periodicity, and the whole family of periodicities subsumed in the zeta function. Sometimes the zeta function is an adequate characterization of topological properties, but often it is not, leaving the remainder of the book to discuss what else is needed.
It is remarkable how much of a semester course on topology has been hidden away here in a little less than fifty pages. Let us look at the cover burb once again: ... "Mathematical prerequisites are relatively modest (mainly linear algebra at the undergraduate level), especially for the first half of the book" ... The problem with topology, really, is not with its list of definitions nor its list of fundamental theorems. Rather, it lies with knowing why they should be used, and gaining experience in consequences. There is the Hardy "Pure Mathematics" approach with deltas and epsilons, and a Bourbaki fondness for theorems as axioms and definitions as theorems.
Case in point: "Lemma 6.2.8. Let M and N be compact metric spaces, and (th):M
(arrow) N be continuous, one-to-one, and onto. Then 
:N (arrow) M is also continuous."
Our authors strike a happy balance between Hardy and Bourbaki: the theorem avoids using words like "surjective" and "injective," but as we read on we had better know the relationship of compactness to convergent subsequences and something about the uniqueness of limits.
This is an excellent book and it is eminently readable. It is just that the computer science student who had the notion that it was not necessary to take the calculus courses had better choose another book (or else go back and fill in some gaps). Facility in thinking topologically is well worth acquiring.
Anyway, in the next paragraph we discover that Hedlund's First Great Theorem means different things to different people. Those who thought that it laid the foundations of cellular automata theory, disabused of their misconception, will find that it actually authorizes the use of sliding block codes.
Only about a third of the chapter is dedicated to the strict business of topological definition; an equal portion describes the zeta function, with a third dedicated to a specialty of one of the authors, the Markov partitions.
Both of these latter concepts are vaguely related to the idea of representing a function as a matrix. Practical difficulty arises because it would require infinite dimensional matrices to represent most mappings, especially to represent the mapping point by point. If the representation were possible, the matrix could be interpreted as the connectivity matrix of a diagram, which would then be analyzed in terms of paths, roots, cycles, leaves and the rest of the vocabulary. In particular, traces connection matrix powers define loops if their points are weighted to make the correspondence work.
Then, an identity relating the determinant of a matrix exponential to the exponential of its trace relates the characteristic polynomial of the matrix to the cycle structure. The exponential of the trace is the zeta function, whose properties derive from the matrix identity. By defining the zeta function directly in terms of cycle counts, difficulties with infinite matrices are avoided.
The matrix identity has been known since the beginning of the century, but the zeta function seems to be an artifact introduced somewhere around the middle of the century, perhaps by Weil or Artin. There are many ways in which the bibliographical notes in the book could be extended, to trace more little historical details such as this one.
Markov partitions derive their origin from trying to dissect a space into subsets, and then to describe the mapping between subsets in matrix form. A laudable objective, it does not always work out in practice. Sometimes a dissection can be shown to be compatible with the given function, to which the section on Markov partitions is dedicated. Linear mappings of integer lattices have provided many practical examples for study. Of course, no mention is made of any matricial representation, setting the discussion directly in the realm of dynamical systems.
From Chapter 7 onward, the book enters another realm.
That might make one wonder, what there is left to mention in Chapter 13, which is entitled "Guide to Advanced Topics?" Mainly, Chapters 7 through 12 could be characterized in terms of what has actually been done in the past quarter century, more or less in the interval since Hedlund wrote his paper on automorphisms and endomorphisms. With that, glimpses of what might remain are available.
Entitled "Conjugacy," Chapter 7 starts out by asking just that: "When are two shifts of finite type conjugate?" Sofic shifts have not even entered the picture just yet. The answer that would be desired would be that, inasmuch as shifts of finite type depend on a connectivity matrix, they would be conjugate whenever the matrices had the same canonical structure.
There are classical results: the work of Frobenius and Perron on positive and non-negative matrices is available, and has been expounded in at least a half dozen widely available and popular textbooks. Linear algebra has had a complete and exhaustive treatment in Halmos' book on "Finite Dimensional Vector Spaces," particular parts on polar forms and square roots and such.
However, applications to Symbolic Dynamics require matrices with integer, and even non-negative integer, elements, which creates inordinate complexity, only gradually and only recently being resolved.
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx