An Introduction to Symbolic Dynamics and Coding
Table of Contents
PREFACE
Chapter 1. SHIFT SPACES
1.1. Full Shifts
1.2. Shift Spaces
1.3. Languages
1.4. Higher Block Shifts and Higher Power Shifts
1.5. Sliding Block Codes
1.6. Convolutional Encoders
Chapter 2. SHIFTS OF FINITE TYPE
2.1. Finite Type Constraints
2.2. Graphs and Their Shifts
2.3. Graph Representations of Shifts of Finite Type
2.4. State Splitting
2.5. Data Storage and Shifts of Finite Type
Chapter 3. SOFIC SHIFTS
3.1. Presentations of Sofic Shifts
3.2. Characterizations of Sofic Shifts
3.3. Minimal Right-Resolving Presentations
3.4. Constructions and Algorithms
Chapter 4. ENTROPY
4.1. Definition and Basic Properties
4.2. Perron-Frobenius Theory
4.3. Computing Entropy
4.4. Irreducible Components
4.5. Cyclic Structure
Chapter 5. FINITE-STATE CODES
5.1. Road Colorings and Right-Closing Labelings
5.2. Finite-State Codes
5.3. Approximate Eigenvectors
5.4. Code Construction
5.5. Sliding Block Decoders
Chapter 6. SHIFTS AS DYNAMICAL SYSTEMS
6.1. Metric Spaces
6.2. Dynamical Systems
6.3. Invariants
6.4. Zeta Functions
6.5. Markov Partitions
Chapter 7. CONJUGACY
7.1. The Decomposition Theorem
7.2. Strong Shift Equivalence
7.3. Shift Equivalence
7.4. Invariants for Shift Equivalence
7.5. Shift Equivalence and the Dimension Group
Chapter 8. FINITE-TO-ONE CODES AND FINITE EQUIVALENCE
8.1. Finite-to-One Codes
8.2. Right-Resolving Codes
8.3. Finite Equivalence
8.4. Right-Resolving Finite Equivalence
Chapter 9. DEGREES OF CODES AND ALMOST CONJUGACY
9.1. The Degree of a Finite-to-One Code
9.2. Almost Invertible Codes
9.3. Almost Conjugacy
9.4. Typical Points According to Probability
Chapter 10. EMBEDDINGS AND FACTOR CODES
10.1. The Embedding Theorem
10.2. The Masking Lemma
10.3. Lower Entropy Factor Codes
Chapter 11. REALIZATION
11.1. Realization of Entropies
11.2. Realization of Zeta Functions
11.3. Pure Subgroups of Dimension Groups
Chapter 12. EQUAL ENTROPY FACTORS
12.1. Right-Closing Factors
12.2. Eventual Factors of Equal Entropy
12.3. Ideal Classes
12.4. Sufficiency of the Ideal Class Condition
Chapter 13. GUIDE TO ADVANCED TOPICS
13.1. More on Shifts of Finite Type and Sofic Shifts
13.2. Automorphisms of Shifts of Finite Type
13.3. Symbolic Dynamics and Stationary Processes
13.4. Symbolic Dynamics and Ergodic Theory
13.5. Sofic-like Shifts
13.6. Continuous Flows
13.7. Minimal Shifts
13.8. One-Sided Shifts
13.9. Shifts with a Countable Alphabet
13.10. Higher Dimensional Shifts
NOTATION INDEX
INDEX
BIBLIOGRAPHY