new books and old articles (15)
The new book now being discussed is "An Introduction to Symbolic Dynamics and Coding" by Douglas Lind and Brian Marcus, recently published by Cambridge University Press. It is intended as a textbook, with numerous exercises and a comprehensible level of presentation, but it is no less a reference work, with its extensive treatment of a wide variety of topics for which a systematic treatment is difficult or impossible to find elsewhere.
Cellular automata are implicitly included in the subject matter; although the whole width and breadth of the subject of cellular automata is hardly present, that is only because the authors' interests and specializations confine them to the reversible and conditionally reversible automata. For that reason, automata theorists will find a wealth of material whose existence they barely suspected.
The previous posting listed the table of contents and summarized the first two chapters. The third chapter is dedicated to sofic systems, where we continue.
Symbolic Dynamics seems to have had a strange history, some of which can be gleaned from the historical notes at the ends of the chapters, and more of which has to be surmised from personal experience or alternative reading. Not having much of the source material readily at hand doesn't help matters either.
The end of the last century saw the culmination of some fields of study, such as complex variable theory or classical mechanics, as well as the emergence of new themes such as relativity or the paradoxes which led to quantum theory. The "solution" of the three body problem via the appearance of Poincare's "New Methods" seems to have opened a new chapter just as much as it closed an old one. The new theory seems to have prospered in some environments just as much as it stagnated in others.
Whatever went on in the twenties and thirties, even as late as the forties and fifties, there seems little reason to dispute the authors' assertion that shifts of finite type began to be studied as such by Parry in the late sixties or by Smale at about the same time. Smale's motivation, at least, still seems to have had connections with the theory of nonlinear differential equations.
Whatever the motives for singling out shifts of finite type, whether it was pure convenience or whether that was the nature of the examples which had been taken as models up until that time, dissatisfactions arose. Credit for the initiative in adopting more general systems seems to go to B. Weiss in the early seventies, some five years later. The route followed by these newly baptized "sofic systems," first based on abstract semigroups, was tortuous and labored. There were intimations that they had something to do with paths in graphs; also that regular expressions were involved.
In Chapter 3 sofic shifts have finally reached a degree of respectability, so that a whole chapter can be devoted to defining them, characterizing them, and even proving theorems pertaining to their combinations.
The title of Chapter 4, "Entropy," would seem to take it out of the smooth flow of chapter titles. But that is because the word entropy means different things to different people, sometimes many things to the same person, few of them related to classical thermodynamics. What we are talking about here is the largest eigenvalue of the connectivity diagram of the matrix which has finally been settled upon. Such a discussion could logically follow the presentation of the matrix itself, so the chapter is not out of place.
By and large, Chapter 4 is a standard recapitulation of the Perron-Frobenius theory of non-negative matrices. At one time, knowledge of this theory was a rarity, but that is no longer so for anyone who works in communication theory, biology, economics, or a variety of other fields. Given that we are reviewing a text book, we are pleased to have found a good place for practicioners of coding theory and other readers to acquire the basic information. It is all here - positivity, eventual positivity, irreducibility, cyclic structure, and even entropy as a proliferation factor.
The fundamental conclusions of the Perron-Frobenius theory are the existence of the dominant eiganvalue, its associated eigenvector, and the alternatives for matrices which are not strictly positive. Dealing with matrix families or equivalence between matrices is a more advanced topic, the preoccupation of some of the later chapters.
Chapter 5 goes into one or two detailed schemes for constructing codes, by which is understood a mapping from the full shift to a subshift. The full shift implies an arbitrary data stream whilst subshifts must meet physical restraints, such as the idiosyncracies of a transmission or storage medium. According to the authors, "This chapter uses most of the concepts discussed in the previous four chapters, and it provides concrete and computable solutions to a variety of coding problems."
Given that information would not be encoded if it could not eventually be recovered, it is easy to appreciate that coding theorists are primarily concerned with reversible or conditionally reversible mappings, whereas cellular automatists see them as special cases, if at all. To each his own, but the difference in emphasis has introduced significant distortions into the two approaches.
The chapters that follow are much more dependent on the topology of symbolic dynamics, and the relationship between topological mappings and algebraic mappings of the connectivity matrices behind sofic shifts and shifts of finite type. However, the relationship between the topology and the matrices does not seem to be as clearly defined as it should be, with the consequence that there may be much preoccupation with things which are not really issues. At the same time, of course, there are some real substantive issues.
The book does not go into these details, but before continuing with the review it may be worthwhile to expound a point of view.
First, although many benefits flow from the use of topology, and there are excellent prospects of discovering many more, it is also true that topology can be a great distraction. One of the principal topological results is Hedlund's (Curtis-Lyndon-Hedlund)'s theorem that continuous, shift-commuting maps of the shift dynamical system are cellular automata. The practical consequence is the use of local maps to define global maps, or in coding theorists use of sliding block maps.
Once the cellular automaton approach has been settled upon, labelled de Bruijn diagrams provide the machinery for discovering their properties; different labellings for different characteristics. They are NOT exclusion matrices for shifts of finite type, but ARE essentially connection matrices for sofic shifts. There is a duality involved, and mostly it is a historical accident that shifts of finite type held the predominant role.
Surjectivity is decided by the subset diagrams of the de Bruijn diagrams, which is also where the influence of the Welch Indices is felt. Uniform multiplicity results from surjectivity, the second important Hedlund theorem.
Amongst other things, pair diagrams derived from de Bruijn diagrams mediate the multiplicities of surjective mappings, isolate reversible mappings, and perform other servives. There is a counterpart of Moore's Garden-of-Eden theorem, but the simplest test of reversibility is "no loops outside the diagonal."
These "other services" have wrought havoc with interpretations of topology. In reading Hedlund's article, be it noted how often (n-1)-separability arises as a concept (basically, the nodes in the de Bruijn diagram), the preoccupation with transitivity, recurrence, periodicity, and a host of other requirements. In Lind and Marcus's book, note the preoccupation with magic words, road coloring problems, left and right resolution, and so on.
The fundamental question is: what shall we do with loops outside the diagonal? If they do not intersect it, they may be harmless, implying a multiplicity of counterimages. If the connection is one-way we have the resolvings, with memory or with anticipation, depending on the direction of the connection.
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx