AN INTRODUTION TO SYMBOLIC DYNAMICS AND CODINGPDF电子书下载

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 Soifc 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.Suffiiciency 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