Table of Contents
An Introduction to Symbolic Dynamics and Coding
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
BACK to Home Page.