## An Introduction to Symbolic Dynamics and CodingSymbolic dynamics is a rapidly growing area of dynamical systems. Although it originated as a method to study general dynamical systems, it has found significant uses in coding for data storage and transmission as well as in linear algebra. This book is the first general textbook on symbolic dynamics and its applications to coding. Mathematical prerequisites are relatively modest (mainly linear algebra at the undergraduate level) especially for the first half of the book. Topics are carefully developed and motivated with many examples, and there are over 500 exercises to test the reader's understanding. The last chapter contains a survey of more advanced topics, and a comprehensive bibliography is included. This book will serve as an introduction to symbolic dynamics for advanced undergraduate students in mathematics, engineering, and computer science. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

SHIFT SPACES | 1 |

12 Shift Spaces | 5 |

13 Languages | 9 |

14 Higher Block Shifts and Higher Power Shifts | 12 |

15 Sliding Block Codes | 15 |

16 Convolutional Encoders | 23 |

SHIFTS OF FINITE TYPE | 28 |

22 Graphs and Their Shifts | 33 |

74 Invariants for Shift Equivalence | 241 |

75 Shift Equivalence and the Dimension Group | 251 |

FINITETOONE CODES AND FINITE EQUIVALENCE | 264 |

82 RightResolving Codes | 275 |

83 Finite Equivalence | 282 |

84 RightResolving Finite Equivalence | 294 |

DEGREES OF CODES AND ALMOST CONJUGACY | 301 |

92 Almost Invertible Codes | 313 |

23 Graph Representations of Shifts of Finite Type | 41 |

24 State Splitting | 49 |

25 Data Storage and Shifts of Finite Type | 58 |

SOFIC SHIFTS | 64 |

32 Characterizations of Sofic Shifts | 70 |

33 Minimal RightResolving Presentations | 75 |

34 Constructions and Algorithms | 86 |

ENTROPY | 99 |

42 PerronFrobenius Theory | 106 |

43 Computing Entropy | 112 |

44 Irreducible Components | 117 |

45 Cyclic Structure | 125 |

FINITESTATE CODES | 136 |

51 Road Colorings and RightClosing Labelings | 137 |

52 FiniteState Codes | 144 |

53 Approximate Eigenvectors | 149 |

54 Code Construction | 156 |

55 Sliding Block Decoders | 164 |

SHIFTS AS DYNAMICAL SYSTEMS | 171 |

61 Metric Spaces | 172 |

62 Dynamical Systems | 183 |

63 Invariants | 187 |

64 Zeta Functions | 192 |

65 Markov Partitions | 201 |

CONJUGACY | 216 |

71 The Decomposition Theorem | 217 |

72 Strong Shift Equivalence | 225 |

73 Shift Equivalence | 233 |

93 Almost Conjugacy | 322 |

94 Typical Points According to Probability | 328 |

EMBEDDINGS AND FACTOR CODES | 337 |

102 The Masking Lemma | 354 |

103 Lower Entropy Factor Codes | 358 |

REALIZATION | 367 |

112 Realization of Zeta Functions | 382 |

113 Pure Subgroups of Dimension Groups | 396 |

EQUAL ENTROPY FACTORS | 402 |

121 RightClosing Factors | 403 |

122 Eventual Factors of Equal Entropy | 411 |

123 Ideal Classes | 416 |

124 Sufficiency of the Ideal Class Condition | 424 |

GUIDE TO ADVANCED TOPICS | 431 |

132 Automorphisms of Shifts of Finite Type | 435 |

133 Symbolic Dynamics and Stationary Processes | 441 |

134 Symbolic Dynamics and Ergodic Theory | 445 |

135 Soficlike Shifts | 450 |

136 Continuous Flows | 453 |

137 Minimal Shifts | 457 |

138 OneSided Shifts | 461 |

139 Shifts with a Countable Alphabet | 463 |

1310 Higher Dimensional Shifts | 466 |

471 | |

486 | |

489 | |

### Other editions - View all

### Common terms and phrases

1-block adjacency assume automorphism called Chapter compact complete component condition conjugacy conjugate consider construction contains continuous corresponding defined Definition denote described determined dynamical systems edge shift eigenvalue eigenvector elements embedding entries entropy eventually Example Exercise extend factor code Figure finite equivalence finite type finite-state finite-to-one given gives graph G Hence infinite initial integral integral matrix invariant invertible irreducible irreducible shift irreducible sofic shift isomorphic labeled graph least Lemma length Let G 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 right-resolving satisfies sequence shift equivalence shift of finite shift space Show sliding block code splitting starting subset Suppose symbolic Theorem transitive unique vector vertex vertices