An Introduction to Symbolic Dynamics and Coding

Cover......Page 1
About......Page 2
An Introduction to Symbolic Dynamics and Coding......Page 6
0521559006......Page 7
Contents......Page 10
Preface......Page 14
§1.1. Full Shifts......Page 20
§1.2. Shift Spaces......Page 24
§1.3. Languages......Page 28
§1.4. Higher Block Shifts and Higher Power Shifts......Page 31
§1.5. Sliding Block Codes......Page 34
§1.6. Convolutional Encoders......Page 42
§2.1. Finite Type Constraints......Page 47
§2.2. Graphs and Their Shifts......Page 52
§2.3. Graph Representations of Shifts of Finite Type......Page 60
§2.4. State Splitting......Page 68
§2.5. Data Storage and Shifts of Finite Type......Page 77
§3.1. Presentations of Sofic Shifts......Page 83
§3.2. Characterizations of Sofic Shifts......Page 89
§3.3. Minimal Right-Resolving Presentations......Page 94
§3.4. Constructions and Algorithms......Page 105
§4.1. Definition and Basic Properties......Page 118
§4.2. Perron-Frobenius Theory......Page 125
§4.3. Computing Entropy......Page 131
§4.4. Irreducible Components......Page 136
§4.5. Cyclic Structure......Page 144
CHAPTER 5. FINITE-STATE CODES......Page 155
§5.1. Road Colorings and Right-Closing Labelings......Page 156
§5.2. Finite-State Codes......Page 163
§5.3. Approximate Eigenvectors......Page 168
§5.4. Code Construction......Page 175
§5.5. Sliding Block Decoders......Page 183
CHAPTER 6. SHIFTS AS DYNAMICAL SYSTEMS......Page 190
§6.1. Metric Spaces......Page 191
§6.2. Dynamical Systems......Page 202
§6.3. Invariants......Page 206
§6.4. Zeta Functions......Page 211
§6.5. Markov Partitions......Page 220
CHAPTER 7. CONJUGACY......Page 235
§7.1. The Decomposition Theorem......Page 236
§7.2. Strong Shift Equivalence......Page 244
§7.3. Shift Equivalence......Page 252
§7.4. Invariants for Shift Equivalence......Page 260
§7.5. Shift Equivalence and the Dimension Group......Page 270
§8.1. Finite-to-One Codes......Page 283
§8.2. Right-Resolving Codes......Page 294
§8.3. Finite Equivalence......Page 301
§8.4. Right-Resolving Finite Equivalence......Page 313
§9.1. The Degree of a Finite-to-One Code......Page 320
§9.2. Almost Invertible Codes......Page 332
§9.3. Almost Conjugacy......Page 341
§9.4. Typical Points According to Probability......Page 347
§10.1. The Embedding Theorem......Page 356
§10.2. The Masking Lemma......Page 373
§10.3. Lower Entropy Factor Codes......Page 377
§11.1. Realization of Entropies......Page 386
§11.2. Realization of Zeta Functions......Page 401
§11.3. Pure Subgroups of Dimension Groups......Page 415
CHAPTER 12. EQUAL ENTROPY FACTORS......Page 421
§12.1. Right-Closing Factors......Page 422
§12.2. Eventual Factors of Equal Entropy......Page 430
§12.3. Ideal Classes......Page 435
§12.4. Sufficiency of the Ideal Class Condition......Page 443
§13.1. More on Shifts of Finite Type and Sofic Shifts......Page 450
§13.2. Automorphisms of Shifts of Finite Type......Page 454
§13.3. Symbolic Dynamics and Stationary Processes......Page 460
§13.4. Symbolic Dynamics and Ergodic Theory......Page 464
§13.5. Sofic-like Shifts......Page 469
§13.6. Continuous Flows......Page 472
§13.7. Minimal Shifts......Page 476
§13.8. One-Sided Shifts......Page 480
§13.9. Shifts with a Countable Alphabet......Page 482
§13.10. Higher Dimensional Shifts......Page 485
BIBLIOGRAPHY......Page 490
NOTATION INDEX......Page 505
INDEX......Page 508