new books and old articles (4)
Date: Sun, 7 Apr 1996 18:28
To: ca@think.comHedlund's paper on endomprphisms and automorphisms of the Shift dynamical system establishes a role for cellular automata although no mention is made of the fact; the connection seems to have been established only after the study of cellular automata gained independent popularity. In fact, merely continuous mappings received considerably less attention than endomorphisms, characterized by the uniform multiplicity theorem and Welch's index theorem, and the automorphism which were an interesting, albeit complicated, special case.
In spite of the meticulous care evident in the paper's presentation, the result seems cumbersome, and lacks motivation. Why, for example, are (n-1)-blocks and (n-1)-separation so important? From another point of view we know that these are the shift registers to which de Bruijn diagrams apply. Can the author have developed such a complicated theory without knowing that?
Another interesting observation is that it is assumed that neighborhoods have odd length, although that does not affect any results; nevertheless it would have changed a notation which is otherwise spelled out in such exquisite detail.
Other authors have wanted examples of subshifts, settling, for whatever reasons, on the so-called Subshifts of Finite Type. Someone may have had an actual application in mind; there was already an analogy with Markov chains in probability theory.
Alternatively, it may have been due to the temptation arising when the abstract definition of the topology of the Shift was consulted and countable exclusions were encountered, to settle for finite exclusion instead. Choosing a matrix to show exclusions focussed attention on that particular matrix, notwithstanding its constituting a less than ideal representative; a deficiency eventually repaired by the invention of Sofic systems. The whole prolonged episode should confer humility on those who think that Hedlund's article was actually a precursor of cellular automata theory. It may well have been, but if so, the route must have been devious.
The model of Subshifts as Flows in a Labelled Graph had an early proponent in
Roland Fischer Sofic Systems and Graphs Monatshefte fuer Mathematik 80 179-186 (1975)but ideas along that line seem to have been most thoroughly elaborated by Masakazu Nasu in a series of more than half a dozen papers dating from the late seventies and early eighties. Some of them are:
Masakazu Nasu "Local Maps Inducing Surjective Global Maps of One-Dimensional Tessellation Automata" Mathematical Systems Theory, 11 327-351 (1978). Masakazu Nasu "Indecomposable Local Maps of Tesselation Automata" Mathematical Systems Theory, 13 81-93 (1979). Masakazu Nasu "An interconnection of local maps inducing onto global maps" Discrete Applied Mathematics 2 125-150 (1980). Masakazu Nasu "Uniformly finite-to-one and onto extensions of homomorphisms between strongly connected graphs" Discrete Mathematics 39 171-197 (1982). Masakazu Nasu "Constant-to-one and onto global maps of homomorphisms between strongly connected graphs" Ergodic Theory and Dynamical Systems 3 387-413 (1983). Masakazu Nasu "An invariant for bounded-to-one factor maps between transitive sofic subshifts" Ergodic Theory and Dynamical Systems 5 89-105 (1985). Masakazu Nasu "Topological conjugacy for sofic systems" Ergodic Theory and Dynamical Systems 6 265-280 (1986).The first of this series is a good place to begin, because that is where the useful definitions and concepts can be found. The article runs 25 pages, which includes six sections and six theorems.
- Introduction
the author cites nine references which are traditional cellular automaton theory from the sixties or early seventies, plus Hedlund's article. Promising a graphical and finite-automata-theoretical approach, he then summarizes the remainder of the article.- Preliminaries
a list of definitions and the citation of three theorems from the literature, including a comprehensive one on uniform multiplicity including its ramifications on configurations quiescent at infinity. The section ends with some graph-theoretic definitions.- Bundle-Graphs and lambda-Bundle-Graphs
after calling the de Bruijn diagram a "string graph," the subset diagram is introduced as a "bundle graph." There are actually two graphs, depending on whether union is taken with respect to in links or out links. The important results are that paths for surjective automata are unique between endpoints in the de Bruijn diagram and generally Hedlund's equivalences hold, even in a more general graph theoretical case depending only on uniformity of indegrees and outdegrees.Welch's indices and maximal compatible extensions are related to the subset diagrams; when the automaton map is an endomorphism, the important results are that all continuations from maximal nodes are maximal, there is a maximal node above each and every unit class, and their level in the subset diagram is given by the L or R indices. TYhe important Theorem 1 asserts that the diagram in the subset graph is well defined (an image of the de Bruijn diagram) just exactly when dealing with an endomprphism.
- CsubF-surjective local maps
Finally, the consequences of quiescence at infinity are examined, and summarized in theorem 2. Some trees are required.- Mergible local maps
- Definite local maps
Even after the subset diagram has been mastered, there seems to be a problem in dealing with the pair diagram. Thus treatments of the shift tend to go into details of which sequences are called closing, resolving, merging, separating, definitie, and so on. Once the pair diagram has been constructed from the de Bruijn diagram, it is necessary to examine its transients, connected components, and the relation of all them to the diagonal; the Welch indices have something to do with the length of transients, just as they relate to levels in the subset diagram. The pair diagram is not used here.- Bibliography of 20 items
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx