Douglas Lind and Brian Marcus, in their book "An Introduction to Symbolic Dynamics and Coding," published last year by Cambridge University Press, have given us a comprehensive treatment of shifts of finite type and sofic shifts, an area which has seen considerable activity since the sixties; one in which they have taken an active part. Maybe a little long for its intended use as a text book, it nevertheless encompasses the literature of recent years in a masterly fashion, unifying a heretofore scattered literature.
Shifts both are and aren't cellular automata. The rules governing shifts make their shift-commuting continuous mappings into cellular automata; Particular shifts are best regarded as restricted classes of configurations, whose behavior under cellular automaton mappings is the topic of interest. Coding theory concerns possible functions between pairs of configurations whereas automata theory foresees the consequences of iterating a function which has already been chosen. Evidently the two activities are intimately related.
We have been summarizing the thirteen chapters of the book, two by two, and so have nearly finished the book, having arrived at Chapter 11. But there are still more than a hundred pages to go. If we hurry, we can finish them up.
"Realization," the title of Chapter 11, reckons with the handful of invariants which have been adduced for shifts - entropy, cyclage, dimension group, and so on. There is a converse question, consisting in knowing their arbitrariness. There are concepts, like prime numbers, which only mathematicians appreciate, but which still cannot be ignored by the rest of the populace. So we find here that there are actually distinctions between entropies which are integers and those not, some are rational yet others not, algebraic or transcendental and so on. Esoteric distinctions at first sight, but vital in applications.
Why this should be so is perhaps not too difficult to perceive: entropies refer to rates of proliferation amongst paths, so integers might well be associated with uniform out-degrees, or with the authors' road coloring problem. Maybe the association isn't quite that simple, but it is plausible; knowing for sure comes back to an exercise in algebra. So that is the content of the first section, "Realization of Entropies."
The second section, "Realization of Zeta Functions," goes a step farther, given that the zeta function depends on traces rather than the dominant eigenvalue alone. From a less algebraic viewpoint, the zeta function depends on a shift's periodicity, but calculated with a particular weighting. No matter; the section still is chock full of algebraic number theory.
The third section, "Pure Subgroups of Dimension Groups," continues the trend from dominant eigenvalue to non-zero spectrum by involving the dimension groups; the question is mostly: "What can be said about a chain of dimension subgroups?" The answer is of some use in the next chapter.
The twelfth, which is the final substantive chapter and entitled "Equal Entropy Factors," ties off a few remaining loose ends. Or, which the authors assert, the loose ends are almost tied down, making the chapter a suitable transition piece into the final prospective. In any event, some more algebraic number theory peeks around the corner.
The sections of the twelfth chapter are:
12.1 Right-Closing Factors
12.2 Eventual Factors of Equal Entropy
12.3 Ideal Classes
12.4 Sufficiency of the Ideal Class Condition
Our reaction to all this is nothing short of amazement: Can resolving the question of two graphs containing the same labelled paths (alternatively, what pairs of paths can be superposed?) really be all this complicated? As consolation, we could recall the demonstrable insolubility of Post's Correspondence Principle and appreciate our good luck.
In their final Chapter 13, "Guide to Advanced Topics," the authors thoughtfully remind us that the show is not yet over, although they do not go quite so far as inviting us back for the second act.
The first section, titled "More on Shifts of Finite Type and Sofic Shifts," lists several additional topics for consideration:
the core matrix
constraints on degrees of finite-to-one factor codes
renewal systems
almost finite type shifts
One of the constraints in the second item is imposed by the multiplicative nature of the Welch indices.
The second section continues with "Automorphisms of Shifts of Finite Type," a whole area to which the monograph "Textile Systems" by Nasu, which has previously been mentioned, is dedicated. Also worthy of note are the papers of Wagoner interpreting the conjugacy relations, especially those depending on the factorization of the connection matrix, as constructs from algebraic topology.
The third section is dedicated to "Symbolic Dynamics and Stationary Processes," It and the fourth, "Symbolic Dynamics and Ergodic Theory," elaborate on the connections hinted at in Chapter 9, that symbolic dynamics can be built up from measure theory as well as from topology.
Section 5 recognizes that there are other shifts, under the heading "Sofic-Like Shifts;" and then there are "Continuous Flows," the topic of Section 6. Section 7 returns to "Minimal Shifts," an historical antecedent which occupied Hedlund, Gottschalk, Birkhoff, Morse, and others. Involved periodicity classifications with which we are still involved date from those times.
Section 8 alludes to "One-Sided Shifts," a subject of considerable historical as well as practical importance. The ladder operators in quantum mechanics, for instance. It would hardly do to omit "Shifts with a Countable Alphabet," particularly if one were a mathematician interested in generality. Pushing just a little bit further, one might encounter coupled map lattices and even probabilistic automata.
The concluding tenth section recognizes "Higher Dimensional Shifts," about which practically nothing is known and yet everyone would like to know something.
Very well, everyone has their favorite wish list. This reviewer's main concern lies in having seen how far an approach which he does not particularly like has advanced. For that, the book has been extremely enlightening, in spite of one's having had most of its references in hand for several years and having studied them with some diligence. Since theorems tend to be true or false independently of whether one likes them or not, any "improved" theory is going to have to account for all these results, even the conjectures, one way or another.
Fortunately, the quibble is not so much with the results, although one would hope to see fewer of them and better organized. Rather, having seen this book, less time needs to be spent in trying to figure out what all those diverse authors really meant; instead effort can go into juggling the little pieces into a better picture.
That, at least, is a personal viewpoint. In the meantime, until another book comes along (there is one on the horizon - "Theory and Applications in Additive Cellular Automata" announced for February 1997 by the IEEE Computer Society) - we will let this series rest for a while, content to repeat the admonition that although the book by Lind and Marcus is not about cellular automata, it comes so close to being so that nobody who is interested in celllular automata should ignore it (Nor, either, those who would just like to learn about coding theory and symbolic dynamics).