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. |
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 2-shift adjacency matrix algebraic alphabet approximate eigenvector automorphism bi-infinite Chapter compact condition conjugacy conjugate construction cylinder sets defined Definition denote doubly transitive points dynamical systems eigenvalue eigenvector embedding encoder entropy eventual factor Example Exercise finite equivalence finite type finite-state code full shift graph G h(XG Hence infinite invariant invertible irreducible component irreducible edge shift irreducible graph irreducible shift irreducible sofic shift isomorphic labeled graph Lemma Let G Markov chain Markov partition metric space minimal right-resolving presentation nonnegative integral one-to-one out-degree out-splitting pair path in G periodic points polynomial pre-images primitive integral primitive integral matrix Proposition prove Recall result road-coloring sequence shift map shift of finite shift space Show sliding block code splitting stationary process strong shift equivalence subset subshift Suppose symbolic dynamics synchronizing word topological unique vector vertex shift vertices zeta function