An Introduction to Symbolic Dynamics and Coding

Front Cover
Cambridge University Press, Nov 24, 1995 - Mathematics - 495 pages
Symbolic dynamics is a rapidly growing area of dynamical systems. Although it originated as a method to study general dynamical systems, it has found significant uses in coding for data storage and transmission as well as in linear algebra. This book is the first general textbook on symbolic dynamics and its applications to coding. Mathematical prerequisites are relatively modest (mainly linear algebra at the undergraduate level) especially for the first half of the book. Topics are carefully developed and motivated with many examples, and there are over 500 exercises to test the reader's understanding. The last chapter contains a survey of more advanced topics, and a comprehensive bibliography is included. This book will serve as an introduction to symbolic dynamics for advanced undergraduate students in mathematics, engineering, and computer science.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

SHIFT SPACES
1
12 Shift Spaces
5
13 Languages
9
14 Higher Block Shifts and Higher Power Shifts
12
15 Sliding Block Codes
15
16 Convolutional Encoders
23
SHIFTS OF FINITE TYPE
28
22 Graphs and Their Shifts
33
74 Invariants for Shift Equivalence
241
75 Shift Equivalence and the Dimension Group
251
FINITETOONE CODES AND FINITE EQUIVALENCE
264
82 RightResolving Codes
275
83 Finite Equivalence
282
84 RightResolving Finite Equivalence
294
DEGREES OF CODES AND ALMOST CONJUGACY
301
92 Almost Invertible Codes
313

23 Graph Representations of Shifts of Finite Type
41
24 State Splitting
49
25 Data Storage and Shifts of Finite Type
58
SOFIC SHIFTS
64
32 Characterizations of Sofic Shifts
70
33 Minimal RightResolving Presentations
75
34 Constructions and Algorithms
86
ENTROPY
99
42 PerronFrobenius Theory
106
43 Computing Entropy
112
44 Irreducible Components
117
45 Cyclic Structure
125
FINITESTATE CODES
136
51 Road Colorings and RightClosing Labelings
137
52 FiniteState Codes
144
53 Approximate Eigenvectors
149
54 Code Construction
156
55 Sliding Block Decoders
164
SHIFTS AS DYNAMICAL SYSTEMS
171
61 Metric Spaces
172
62 Dynamical Systems
183
63 Invariants
187
64 Zeta Functions
192
65 Markov Partitions
201
CONJUGACY
216
71 The Decomposition Theorem
217
72 Strong Shift Equivalence
225
73 Shift Equivalence
233
93 Almost Conjugacy
322
94 Typical Points According to Probability
328
EMBEDDINGS AND FACTOR CODES
337
102 The Masking Lemma
354
103 Lower Entropy Factor Codes
358
REALIZATION
367
112 Realization of Zeta Functions
382
113 Pure Subgroups of Dimension Groups
396
EQUAL ENTROPY FACTORS
402
121 RightClosing Factors
403
122 Eventual Factors of Equal Entropy
411
123 Ideal Classes
416
124 Sufficiency of the Ideal Class Condition
424
GUIDE TO ADVANCED TOPICS
431
132 Automorphisms of Shifts of Finite Type
435
133 Symbolic Dynamics and Stationary Processes
441
134 Symbolic Dynamics and Ergodic Theory
445
135 Soficlike Shifts
450
136 Continuous Flows
453
137 Minimal Shifts
457
138 OneSided Shifts
461
139 Shifts with a Countable Alphabet
463
1310 Higher Dimensional Shifts
466
BIBLIOGRAPHY
471
NOTATION INDEX
486
INDEX
489
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information