"An Introduction to Symbolic Dynamics and Coding" by Douglas Lind and Brian Marcus, published by Cambridge University Press, is a book which means what it says, in the sense that it is a thoroughgoing exposition of material to be found in the literature of symbolic dynamics over the past thirty years. Much of this is research was performed by the authors themselves, but the book goes much farther than that, making it a very readable presentation of the whole entire subject.
Although cellular automata receive the most extremely casual notice, the fact remains that the treatment has the most detailled possible applications to cellular automata, particularly with respect to the borderline between reversible automata and the others. The book takes great pains to introduce topology and to explain it, a feature conspicuously lacking in the journal articles on which it is based. Nevertheless, the reader whose grounding lies in automata theory will find an entirely different point of view, with its own traditions, language, and priorities.
For the most part, cellular automata theory starts with the definition of its working materials - states, lattice, rule of evolution - and goes on to examine all kinds of particular examples and classify them before finally turning to an organized theory. With symbolic dynamics, structure seems to have the highest priority, sometimes to the extent that examples are never contemplated; at most maybe to provide a counterexample or two. There is another important difference: whereas reversibility is one of many properties of an automaton which merit attention, it is first, foremost, and seemingly the only characteristic of dynamical systems which seems to garner interest.
It is in keeping with the systems dynamical viewpoint that the first part of the book explains concepts like the full shift, subshifts of finite type, and sofic systems, in considerable detail, relating them to specific kinds of graphs; even including a respectable introduction to the theory of graphs (directed graphs), About the only thing missing is the definition of a dual graph, but it soon becomes apparent that such operations as state splitting and the introduction of division matrices and amalgamation matrices are very much involved with the calculation of duals.
Sometimes a dual graph is called an edge graph, which is a term the authors use liberally. However, the essence of the dual transformation consists in one specific factorization and reassembly of the connection matrix when the factors are multiplied in the opposite order. Repetition produces a dual tower, but it is not always possible to run the process backwards; certain supplementary conditions must be met. Not to be overlooked is the similarity of the construction of the dual tower to the formation of the higher block presentations, both of which are intimately related to the presence of paths in the basic graph.
Bearing in mind the relationship that sometimes exists between the sequences in a shift space, paths through a graph, and the algebraic properties of its connection matrix, it is time to examine Chapter 7, Conjugacy. Several levels of relationship have to be taken into account because algebra, topology, and indexing are all there. The basic concept is that a function f between two systems A and B, themselves with structures a and b, should satisfy a f = f b, something which is often depicted in a commuting category theory diagram. The trick lies in giving the symbols concrete meaning.
The chapter opens with an innocuous pair of 2x2 integer matrices, and the question of whether they are conjugate? It is a good example to bear in mind as the theory unfolds, and is used several times in the text.
The first section estasblished the Decomposition Theorem, which follows readily enough given the previous preparation; it requires a conjugacy to factor into specific components, that resemble duality. The second section gives the dual tower an algebraic form, very reminiscent of the LR scheme for diagonalizing matrices. The third section introduces a variant process which makes two matrices equivalent when they have a common factorization but with the factors in the opposite orders.
Although the usual course on matrix algebra may not emphasize these relationships, they are implicit in such standard sources as Halmos' Introduction to Finite Dimensional Hilbert Spaces. The context of graph theory replaces the field of complex coefficients with the positive integers, which aren't even a ring, making the results more complicated and requiring fresh proofs.
Example 7.3.12 answers the question posed in the introduction to the chapter by exhibiting a tower of length 7, commenting that there is a whole family of matrix pairs whose relationship is still unknown.
The fourth section surveys the results from linear algebra which retain their validity, while introducing some group theory of its own. The Jordan form remains, as well as the Smith form for integral matrices. The fifth section introduces an entirely new concept, which is called the dimension group. Basically, it seems to result from giving positive (or nonnegative) matrices a place to work out their idiosyncracies by asking which vectors they eventually place on an integer lattice after multiple iteration, and which of those are positive.
The authors have done a good job of explaining these ideas; hitherto it has been necessary to cull them from a mass of journal articles. Even if is hard to grasp the deeper significance of all the definitions, at least they are laid out in a form where they can be examined. One gets the idea that somehow iteration is being used to turn the carrier space of the connection matrix into a shift sequence maybe akin to the original.
The chapter closes with a flow chart relating all the different theorems and the different kinds of equivalence which they embody.
In Chapter 8 we find out that if we had been talking about cellular automata, we would have been talking about reversible cellular automata, and that they are just about the hardest ones to deal with. Next in line of succession comes surjective automata, which are not reversible because of multiplicity. If some way could be found to defeat multiplicity, reversibility would prevail. One approach is topological; Hedlund's version. Yet another is statistical, since it sometimes happens that the set of sequences which fails Hedlund's criterion has measure zero. But we are getting ahead of the game.
The title of Chapter 8 is "Finite-to-One Codes and Finite Equivalence," with four sections: 1. Finite-to-One Codes, defining the concept, and relating it to right resolution, which would give it a high Welch R Index. Theorem 8.1.16 about bubbles could be recognized as Moore's Garden-of-Eden Theorem, and the general discussion as deriving from Hedlund's Second Great Theorem, namely the Uniform Multiplicity Theorem.
Section 2 takes up the case of Right-Resolving Codes, with section 3 devoted to Finite Equivalence, an interesting concept from Universal Algebra having to do with ordering functions according to the equivalence relation induced by counterimages, and finding the least upper bound of a pair of functions. Section 4 combines the previous two titles under the heading "Right Resolving Finite Equivalence," all of which is done for the sake of obtaining a lesser, but more tractable (computable), kind of equivalence.
There is no lack of advanced and sophisticated concepts in these later chapters. As well as more familiar concepts: the Pair Diagram makes a brief appearance in Section 3 under the appelation "fiber product," so we know that we are getting close to the arena in which all the distinctions between endomorphisms and automorphisms are played out. There are also hints of the Third Great Theorem, but let it emerge in the remaining chapters.
Still it is hard not to wonder if the presentation could have taken another direction, with another orientation. We are only beginning to appreciate the publisher's understatement of the situation: ... "Mathematical prerequisites are relatively modest [...], especially for the first half of the book." ...