An Introduction to Symbolic Dynamics and CodingSymbolic dynamics is a mature yet rapidly developing area of dynamical systems. It has established strong connections with many areas, including linear algebra, graph theory, probability, group theory, and the theory of computation, as well as data storage, statistical mechanics, and $C^*$-algebras. This Second Edition maintains the introductory character of the original 1995 edition as a general textbook on symbolic dynamics and its applications to coding. It is written at an elementary level and aimed at students, well-established researchers, and experts in mathematics, electrical engineering, and computer science. Topics are carefully developed and motivated with many illustrative examples. There are more than 500 exercises to test the reader's understanding. In addition to a chapter in the First Edition on advanced topics and a comprehensive bibliography, the Second Edition includes a detailed Addendum, with companion bibliography, describing major developments and new research directions since publication of the First Edition. |
Contents
| 1 | |
CHAPTER 2 SHIFTS OF FINITE TYPE | 28 |
CHAPTER 3 SOFIC SHIFTS | 64 |
CHAPTER 4 ENTROPY | 100 |
CHAPTER 5 FINITESTATE CODES | 137 |
CHAPTER 6 SHIFTS AS DYNAMICAL SYSTEMS | 172 |
CHAPTER 7 CONJUGACY | 217 |
CHAPTER 8 FINITETOONE CODES AND FINITE EQUIVALENCE | 265 |
CHAPTER 11 REALIZATION | 369 |
CHAPTER 12 EQUAL ENTROPY FACTORS | 402 |
CHAPTER 13 GUIDE TO ADVANCED TOPICS | 430 |
ADDENDUM | 471 |
BIBLIOGRAPHY | 515 |
ADDENDUM BIBLIOGRAPHY | 531 |
| 541 | |
| 544 | |
CHAPTER 9 DEGREES OF CODES AND ALMOST CONJUGACY | 302 |
CHAPTER 10 EMBEDDINGS AND FACTOR CODES | 338 |
Other editions - View all
Common terms and phrases
algebraic assume automorphism called Chapter closed compact complete component compute condition conjugacy conjugate consider construction contains continuous corresponding defined Definition denote described determined dimension dynamical systems edge shift eigenvalue eigenvector elements embedding entropy eventually Example Exercise extended factor code Figure finite equivalence finite type finite-state finite-to-one function given gives graph G Hence infinite initial integral integral matrix invariant irreducible irreducible shift isomorphic labeled graph least Lemma length Let G Markov matrix minimal mixing nonnegative Note notion Observe obtained pair partition path periodic periodic points Perron positive primitive probability problem proof properties Proposition prove Recall result right-closing sequence shift equivalence shift of finite shift space Show sliding block code splitting starting subset Suppose symbolic Theorem theory topological transitive unique vector vertex vertices