UK Nonlinear News, May 1999

# Symbolic Dynamics: one-sided, two-sided and countable state Markov shifts

## By Bruce P. Kitchens

### Reviewed by Rua Murray

Springer-Verlag, 1998.

Before approaching this book, my acquaintance with Symbolic Dynamics was, like many in the nonlinear dynamics community, that it offered useful tools for describing complicated behaviour in hyperbolic dynamical systems. It was therefore an unexpected pleasure to read this concise and well-written treatment of the more theoretical aspects of the subject. According to the cover, this volume offers

"...a thorough introduction to the dynamics of one-sided and two-sided Markov shifts on a finite alphabet and to the basic properties of Markov shifts on a countable alphabet....[which] is written for graduate students and others who use symbolic dynamics as a tool to study more general systems."

I would go further: this book gives a clear and efficient treatment of an intrinsically interesting subject and would be a valuable addition to any dynamicist's mathematical library.

The basic objects of symbolic dynamics are infinite or doubly infinite sequences of symbols from a fixed alphabet, together with the shift operation on those sequences. The introductory chapter begins with these basic definitions, and then devotes an early section to a collection of standard examples which illustrate the importance of symbolic models in dynamical systems and coding: tent maps, the standard Cantor set, Smale's horseshoe, run-length limited codes. Since the book mainly considers subshifts of finite type (with the exception of the treatment of sofic systems in Section 6.1), repeated use is made of the Perron-Frobenius theory of positive matrices. Pleasingly, a succinct account is included up-front in chapter one. The next three chapters form the bulk of the treatment of finite state shifts, covering topological conjugacy, the classification of subshifts of finite type, shift equivalence, automorphism groups, embeddings and factor maps. Each chapter concludes with some brief but useful notes and references describing the historical development of the material. Chapter five gives a nice treatment of "almost-topological conjugacy", culminating in a constructive proof of the fact that two irreducible subshifts of finite type are topologically almost conjugate if and only if they have the same topological entropy and period. Sufficient conditions for topological conjugacy are unknown.

In chapter six, the emphasis shifts to describe a number of additional topics outside the main body of the theory. Section 6.1 describes the theory of sofic systems (the continuous images of subshifts of finite type). Section 6.2 discusses the connections between Markov chains and subshifts of finite type, and concludes with a symbolic version of the variational principle of ergodic theory: namely the existence of a unique "maximal" Markov measure whose measure theoretic entropy is the topological entropy of the shift. After brief sections on Markov subgroups and cellular automata, section 6.5 gives a thorough and concise account of the connections between symbolic dynamics and coding theory. Finally, Chapter 7 is concerned with subshifts over a countably infinite alphabet. The theory here is much less developed, and accordingly this topic occupies only the final 20% of the book. The first part of the chapter is devoted to extending the Perron-Frobenius theory to infinite positive matrices, and the remainder of the chapter extends the existence results for maximal measures to the infinite state case. The main results are more delicate than for finite state shifts (cf. section 6.2), with dependence on the recurrence properties of the (infinite) transition matrix.

The book is well organised and clearly written, being succinct, comprehensive and well motivated. Indeed, the only criticism I could make is that no mention is made of applications of the countable state theory. However, considering that this book is an expository text about a fascinating and maturing branch of abstract mathematics, this is not a particularly serious complaint. Overall, this book is interesting and ought to be accessible to graduate students with a strong mathematical background. Consequently, this text is well worth adding to any research library.

UK Nonlinear News thanks Springer-Verlag for providing a copy of this book for review.

Rua Murray ( rua@Math.UVic.CA),
University of Victoria, BC