There is another new book which should be of considerable interest to anyone working with celllular automata theory, even though the title and orientation of the book are totally toward symbolic dynamics and coding.
Douglas Lind and Brian Marcus
An Introduction to Symbolic Dynamics and Coding
Cambridge University Press 1995
ISBN 0-521-55900-6 (paperback)
ISBN 0-521-55124-2 (hardback)
Chapter 1. Shift Spaces................................23 pages
Chapter 2. Shifts of Finite Type. 30 pages
Chapter 3. Sofic Shifts. 22 pages
Chapter 4. Entropy.....................................26 pages
Chapter 5. Finite-State Codes. 28 pages
Chapter 6. Shifts as Dynamical Systems. 30 pages
Chapter 7. Conjugacy...................................35 pages
Chapter 8. Finite-to-one Codes and Finite Equivalence. 30 pages
Chapter 9. Degrees of Codes and Almost Conjugacy. 27 pages
Chapter 10. Embeddings and Factor Codes.................21 pages
Chapter 11. Realization. 29 pages
Chapter 12. Equal Entropy Factors. 22 pages
Chapter 13. Guide to Advanced Topics....................35 pages
Bibliography 15 pages (approx 380 items)
Cellular automata receive little more than passing references, the most recent of which are to the proceedings of the first Los Alamos conference and the proceedings edited by Demongeot, Goles and Tchuente (for which they at least spelled the name of the first author correctly). Small wonder, the book being oriented towards endomorphisms and automorphisms of the Shift, the topic of Hedlund's classical paper.
In spite of that, it really IS a book about cellular automata, and one which ought to be read by anyone seriously interested in the subject. Not the least of the factors reccommending it is its expository style; while it is intended as a textbook with numerous examples (its actual origin, in fact), the result is far more illuminating than oppressive, and stands in marked contrast to Hedlund's well known style on the one hand, and thousand-page calculus texts which can be found on the market, at the other extreme. .
Wolfram, in his World Scientific reprint collection, introduction to the bibliography, remarks: "The cellular automaton literature is diverse not only in content but in origins. Cellular automata have been invented independently many times, and in many cases, independent parts of the literature have developed."
Many people see a tradition of cellular automata extending back to von Neumann, but this book by Lind and Marcus belongs to the lore of mathematical communications theory as exemplified by the work of Shannon, and related to such electrical engineering topics as coding, error detection and correction, and to an extent, cryptography. These areas have been heavily influenced by Hedlund's exposition of the Shift Dynamical System, which in turn has its roots in the work of Poincare, Birkhoff, and such things as the Ergodic Theorem.
Symbolic dynamicists have rarely resisted the temptation to assert that cellular automata theory is just a special case (thanks to Hedlund's first great theorem) and cellular automatists have adopted the practice of citing Hedlund's article sight unseen, either out of a feeling that it is the right thing to do, or because it makes a good marker for Citation Index. So we can welcome this new book for laying the cards out on the table, where the possible relationships can be examined and evaluated.
The first chapter introduces the basic definitions, such as a sequence, a sequence space, and the relevance of the shift. But even at this very earliest stage, the idea of forbidden blocks and a shift of finite type is injected straight into the theory. That brings up the concept of languages and grammars, and pictorial representations of sequences. De Bruijn diagrams are here, under the guise of "higher block shifts" as are the "higher power shifts" where the blocks are contiguous rather than overlapping. The "local map" of cellular automaton theory makes its appearance as a "sliding block code" together with such variants as expressing the mapping as a polynomial in a finite field, and the subclass of convolution codes. It is apparent from the outset that there will be a premium placed on manageable mappings, meaning reversible, error correctible, and the like.
The second chapter is devoted to the all-important concept of a "shift of finite type." At first sight, it is both a very simple concept and a very natural one. We haven't actually seen Hadamard's use of shifts of finite type to define orbits in a space of constant negative curvature, but the mathematical literature is not lacking in examples of a similar nature. If memory serves, higher geometry encounters a similar construction with pedal triangles. Even the prototypical Cantor Set is defined by excluding 1's from the trinary expansion of numbers which would be sequences taken from the set (0, 1, 2).
A matrix definition can be given for a shift of finite type, so it is not surprising that an enormous effort has been expended on relating properties of the defining matrix to properties of its dynamical system. But the second chapter is only just defining the concept; most of its content consists in discussing properties of graphs, connectivity matrices, and transformations to which they can be subjected.
"State splitting," which underlies much of the authors' publications and their applications of coding theory, is introduced here. However, the concept of a dual graph does not seem to be mentioned, so there may be some roundabout presentations and inconveniences as the treatment advances. Premonitions of what is to come are found as distinctions begin to be made between vertex graphs and edge graphs. Nevertheless, let us not lose sight of the fact that the authors are clearly laying out the theory in the way that many prople understand and practice it.
For the purposes of automata theory, probably the most important item to be emphasized is that shifts of finite type have little to do with automata. They represent a means of defining a certain class of configurations, whose evolution automata theory would want to examine. But there are alternative classes of configurations, such as those defined by one sort of formal language or another, which are equally worthy of consideration; indeed recent literature contains specific examples.
The chickens finally begin to gather about the roost in Chapter 3, which is devoted to sofic systems. Sofic systems have a great deal more to do with automata theory than shifts of finite type, but it apparently took quite a while for the connection to become evident. Just what, if anything, is or was the problem with shifts of finite type? Basically, if one takes pure symbolic dynamics as outlined by Hedlund, the continuous, shift-commuting mappings (which are coextensive with the class of cellular automata) are defined by a countable list of exclusions.
Well, finite is an instance of countable, and representable by that exclusion matrix, so it was taken up as an object worthy of study. Notwithstanding the fact that early examples were actually based on finite exclusions, the Notes which close each chapter suggest that the explicit term was created by Stephen Smale and cite a reference. Well, it couldn't have been as simple as that, but for those far from the halls of Berkeley, such statements and citations have to suffice.
Going ahead with cellular automata, the result is that de Bruijn diagrams contain the keys to their evolution, although the information gets extracted by labelling the diagram. Hence one wants to talk about labelled graphs, and the natural entity is actually the dual of the connection matrix of the shifts of finite type. But not every graph is a dual, and thereby hangs a tale.