《AN INTRODUTION TO SYMBOLIC DYNAMICS AND CODING》

CHAPTER 1.SHIFT SPACES1

1.1.Full Shifts1

1.2.Shift Spaces5

1.3.Languages9

1.4.Higher Block Shifts and Higher Power Shifts12

1.5.Sliding Block Codes15

1.6.Convolutional Encoders23

CHAPTER 2.SHIFTS OF FINITE TYPE28

2.1.Finite Type Constraints28

2.2.Graphs and Their Shifts33

2.3.Graph Representations of Shifts of Finite Type41

2.4.State Splitting49

2.5.Data Storage and Shifts of Finite Type58

CHAPTER 3.SOFIC SHIFTS64

3.1.Presentations of Sofic Shifts64

3.2.Characterizations of Soifc Shifts70

3.3.Minimal Right-Resolving Presentations75

3.4.Constructions and Algorithms86

CHAPTER 4.ENTROPY99

4.1.Definition and Basic Properties99

4.2.Perron—Frobenius Theory106

4.3.Computing Entropy112

4.4.Irreducible Components117

4.5.Cyclic Structure125

CHAPTER 5.FINITE-STATE CODES136

5.1.Road Colorings and Right-Closing Labelings137

5.2.Finite-State Codes144

5.3.Approximate Eigenvectors149

5.4.Code Construction156

5.5.Sliding Block Decoders164

CHAPTER 6.SHIFTS AS DYNAMICAL SYSTEMS171

6.1.Metric Spaces172

6.2.Dynamical Systems183

6.3.Invariants187

6.4.Zeta Functions192

6.5.Markov Partitions201

CHAPTER 7.CONJUGACY216

7.1.The Decomposition Theorem217

7.2.Strong Shift Equivalence225

7.3.Shift Equivalence233

7.4.Invariants for Shift Equivalence241

7.5.Shift Equivalence and the Dimension Group251

CHAPTER 8.FINITE-TO-ONE CODES AND FINITE EQUIVALENCE264

8.1.Finite-to-One Codes264

8.2.Right-Resolving Codes275

8.3.Finite Equivalence282

8.4.Right-Resolving Finite Equivalence294

CHAPTER 9.DEGREES OF CODES AND ALMOST CONJUGACY301

9.1.The Degree of a Finite-to-One Code301

9.2.Almost Invertible Codes313

9.3.Almost Conjugacy322

9.4.Typical Points According to Probability328

CHAPTER 10.EMBEDDINGS AND FACTOR CODES337

10.1.The Embedding Theorem337

10.2.The Masking Lemma354

10.3.Lower Entropy Factor Codes358

CHAPTER 11.REALIZATION367

11.1.Realization of Entropies367

11.2.Realization of Zeta Functions382

11.3.Pure Subgroups of Dimension Groups396

CHAPTER 12.EQUAL ENTROPY FACTORS402

12.1.Right-Closing Factors403

12.2.Eventual Factors of Equal Entropy411

12.3.Ideal Classes416

12.4.Suffiiciency of the Ideal Class Condition 424

CHAPTER 13.GUIDE TO ADVANCED TOPICS431

13.1.More on Shifts of Finite Type and Sofic Shifts431

13.2.Automorphisms of Shifts of Finite Type435

13.3.Symbolic Dynamics and Stationary Processes441

13.4.Symbolic Dynamics and Ergodic Theory445

13.5.Sofic-like Shifts450

13.6.Continuous Flows453

13.7.Minimal Shifts457

13.8.One-Sided Shifts461

13.9.Shifts with a Countable Alphabet463

13.10.Higher Dimensional Shifts466

BIBLIOGRAPHY471

NOTATION INDEX486

INDEX489