CHAPTER 1.SHIFT SPACES 1
1.1.Full Shifts 1
1.2.Shift Spaces 5
1.3.Languages 9
1.4.Higher Block Shifts and Higher Power Shifts 12
1.5.Sliding Block Codes 15
1.6.Convolutional Encoders 23
CHAPTER 2.SHIFTS OF FINITE TYPE 28
2.1.Finite Type Constraints 28
2.2.Graphs and Their Shifts 33
2.3.Graph Representations of Shifts of Finite Type 41
2.4.State Splitting 49
2.5.Data Storage and Shifts of Finite Type 58
CHAPTER 3.SOFIC SHIFTS 64
3.1.Presentations of Sofic Shifts 64
3.2.Characterizations of Sofic Shifts 70
3.3.Minimal Right-Resolving Presentations 75
3.4.Constructions and Algorithms 86
CHAPTER 4.ENTROPY 99
4.1.Definition and Basic Properties 99
4.2.Perron-Frobenius Theory 106
4.3.Computing Entropy 112
4.4.Irreducible Components 117
4.5.Cyclic Structure 125
CHAPTER 5.FINITE-STATE CODES 136
5.1.Road Colorings and Right-Closing Labelings 137
5.2.Finite-State Codes 144
5.3.Approximate Eigenvectors 149
5.4.Code Construction 156
5.5.Sliding Block Decoders 164
CHAPTER 6. SHIFTS AS DYNAMICAL SYSTEMS 171
6.1. Metric Spaces 172
6.2. Dynamical Systems 183
6.3. Invariants 187
6.4. Zeta Functions 192
6.5. Markov Partitions 201
CHAPTER 7. CONJUGACY 216
7.1. The Decomposition Theorem 217
7.2. Strong Shift Equivalence 225
7.3. Shift Equivalence 233
7.4. Invariants for Shift Equivalence 241
7.5. Shift Equivalence and the Dimension Group 251
CHAPTER 8. FINITE-TO-ONE CODES AND FINITE EQUIVALENCE 264
8.1. Finite-to-One Codes 264
8.2. Right-Resolving Codes 275
8.3. Finite Equivalence 282
8.4. Right-Resolving Finite Equivalence 294
CHAPTER 9. DEGREES OF CODES AND ALMOST CONJUGACY 301
9.1. The Degree of a Finite-to-One Code 301
9.2. Almost Invertible Codes 313
9.3. Almost Conjugacy 322
9.4. Typical Points According to Probability 328
CHAPTER 10. EMBEDDINGS AND FACTOR CODES 337
10.1. The Embedding Theorem 337
10.2. The Masking Lemma 354
10.3. Lower Entropy Factor Codes 358
CHAPTER 11. REALIZATION 367
11.1. Realization of Entropies 367
11.2. Realization of Zeta Functions 382
11.3. Pure Subgroups of Dimension Groups 396
CHAPTER 12. EQUAL ENTROPY FACTORS 402
12.1. Right-Closing Factors 403
12.2. Eventual Factors of Equal Entropy 411
12.3. Ideal Classes 416
12.4. Sufficiency of the Ideal Class Condition 424
CHAPTER 13. GUIDE TO ADVANCED TOPICS 431
13.1. More on Shifts of Finite Type and Sofic Shifts 431
13.2. Automorphisms of Shifts of Finite Type 435
13.3. Symbolic Dynamics and Stationary Processes 441
13.4. Symbolic Dynamics and Ergodic Theory 445
13.5. Sofic-like Shifts 450
13.6. Continuous Flows 453
13.7. Minimal Shifts 457
13.8. One-Sided Shifts 461
13.9. Shifts with a Countable Alphabet 463
13.10. Higher Dimensional Shifts 466
BIBLIOGRAPHY 471
NOTATION INDEX 486
INDEX 489