1 Introduction 1
1.1 Dynamical Systems 2
1.1.1 Phase Space and Orbits 2
1.1.2 Parameters and Bifurcation of Dynamical Behavior 3
1.1.3 Examples of Dynamical Systems 3
1.2 Symbolic Dynamics as Coarse-Grained Description of Dynamics 6
1.2.1 Fine-Grained and Coarse-Grained Descriptions 7
1.2.2 Symbolic Dynamics as the Simplest Dynamics 8
1.3 Abstract versus Applied Symbolic Dynamics 10
1.3.1 Abstract Symbolic Dynamics 10
1.3.2 Applied Symbolic Dynamics 11
1.4 Literature on Symbolic Dynamics 13
2 Symbolic Dynamics of Unimodal Maps 16
2.1 Symbolic Sequences in Unimodal Maps 18
2.1.1 Numerical Orbit and Symbolic Sequence 19
2.1.2 Symbolic Sequence and Functional Composition 26
2.1.3 The Word-Lifting Technique 27
2.2 The Quadratic Map 29
2.2.1 An Over-Simplified Population Model 29
2.2.2 Bifurcation Diagram of the Quadratic Map 31
2.2.3 Dark Lines in the Bifurcation Diagram 37
2.3 Ordering of Symbolic Sequences and the Admissibility Condition 43
2.3.1 Property of Monotone Functions 44
2.3.2 The Ordering Rule 45
2.3.3 Dynamical Invariant Range and Kneading Sequence 49
2.3.4 The Admissibility Condition 51
2.4 The Periodic Window Theorem 54
2.4.1 The Periodic Window Theorem 54
2.4.2 Construction of Median Words 57
2.4.3 The MSS Table of Kneading Sequences 59
2.4.4 Nomenclature of Unstable Periodic Orbits 61
2.5 Composition Rules 62
2.5.1 The*-Composition 63
2.5.2 Generalized Composition Rule 67
2.5.3 Proof of the Generalized Composition Rule 70
2.5.4 Applications of the Generalized Composition Rule 73
2.5.5 Further Remarks on Composition Rules 77
2.6 Coarse-Grained Chaos 79
2.6.1 Chaos in the Surjective Unimodal Map 80
2.6.2 Chaos in ρλ∞Maps 87
2.7 Topological Entropy 95
2.8 Piecewise Linear Maps and Metric Representation of Symbolic Sequences 97
2.8.1 The Tent Map and Shift Map 97
2.8.2 Theλ-Expansion of Real Numbers 98
2.8.3 Characteristic Function of the Kneading Sequence 99
2.8.4 Mapping of Subintervals and the Stefan Matrix 100
2.8.5 Markov Partitions and Generating Partitions 107
2.8.6 Metric Representation of Symbolic Sequences 111
2.8.7 Piecewise Linear Expanding Map 115
3 Maps with Multiple Critical Points 117
3.1 General Discussion 119
3.1.1 The Ordering Rule 120
3.1.2 Construction of a Map from a Given Kneading Sequence 120
3.2 The Antisymmetric Cubic Map 121
3.2.1 Symbolic Sequences and Their Ordering 124
3.2.2 Admissibility Conditions 125
3.2.3 Generation of Superstable Median Words 129
3.3 Symmetry Breaking and Restoration 135
3.3.1 Symmetry Breaking of Symmetric Orbits 137
3.3.2 Analysis of Symmetry Restoration 140
3.4 The Gap Map 143
3.4.1 The Kneading Plane 146
3.4.2 Contacts of Even-Odd Type 149
3.4.3 Self-Similar Structure in the Kneading Plane 151
3.4.4 Criterion for Topological Chaos 155
3.5 The Lorenz-Like Map 159
3.5.1 Ordering Rule and Admissibility Conditions 159
3.5.2 Construction of the Kneading Plane 160
3.5.3 Contacts and Intersections 161
3.5.4 Farey and Doubling Transformations 162
3.6 General Cubic Maps 163
3.6.1 Skeleton，Bones and Joints in Kneading Plane 165
3.6.2 The Construction of the Kneading Plane 169
3.6.3 The*-Composition Rules 173
3.6.4 The Down-Up-Down Type Cubic Map 174
3.7 The Sine-Square Map 178
3.7.1 Symbolic Sequences and Word-Lifting Technique 179
3.7.2 Ordering Rule and Admissibility Conditions 181
3.7.3 Generation of Kneading Sequences 182
3.7.4 Joints and Bones in the Kneading Plane 184
3.7.5 Skeleton of Superstable Orbits and Existence of Topological Chaos 188
3.8 The Lorenz-Sparrow Maps 190
3.8.1 Ordering and Admissibility of Symbolic Sequences 190
3.8.2 Generation of Compatible Kneading Pairs 193
3.8.3 Generation of Admissible Sequences for a Given Kneading Pair 194
3.8.4 Metric Representation of Symbolic Sequences 196
3.8.5 One-Parameter Limits of Lorenz-Sparrow Maps 197
3.9 Piecewise Linear Maps 198
3.9.1 Piecewise Linear Maps with Multiple Critical Points 199
3.9.2 Kneading Determinants 200
4 Symbolic Dynamics of Circle Maps 203
4.1 The Physics of Linear and Nonlinear Oscillators 205
4.2 Circle Maps and Their Lifts 206
4.2.1 The Rigid Rotation—Bare Circle Map 207
4.2.2 The Sine-Circle Map 209
4.2.3 Lift of Circle Maps 210
4.2.4 Rotation Number and Rotation Interval 212
4.2.5 Arnold Tongues in the Parameter Plane 214
4.3 Continued Fractions and Farey Tree 215
4.3.1 Farey Tree：Rational Fraction Representation 215
4.3.2 Farey Tree：Continued Fraction Representation 216
4.3.3 Farey Tree：Farey Addresses and Farey Matrices 219
4.3.4 More on Continued Fractions and Farey Representations 222
4.3.5 Farey Tree：Symbolic Representation 226
4.4 Farey Transformations and Well-Ordered Orbits 229
4.4.1 Well-Ordered Symbolic Sequences 230
4.4.2 Farey Transformations as Composition Rules 231
4.4.3 Extreme Property of Well-Ordered Periodic Sequences 232
4.4.4 Generation of R°max and L°min 235
4.5 Circle Map with Non-Monotone Lift 238
4.5.1 Symbolic Sequences and Their Continuous Transformations 238
4.5.2 Ordering Rule and Admissibility Condition 240
4.5.3 Existence of Well-Ordered Symbolic Sequences 240
4.5.4 The Farey Transformations 242
4.5.5 Existence of Symbolic Sequence without Rotation Number 243
4.6 Kneading Plane of Circle Maps 244
4.6.1 Arnold Tongue with Rotation Number 1/2 244
4.6.2 Doubly Superstable Kneading Sequences：Joints and Bones 246
4.6.3 Generation of Kneading Sequences Kg and Ks 247
4.6.4 Construction of the Kneading Plane 249
4.7 Piecewise Linear Circle Maps and Topological Entropy 251
4.7.1 The Sawtooth Circle Map 251
4.7.2 Circle Map with Given Kneading Sequences 252
4.7.3 Kneading Determinant and Topological Entropy 253
4.7.4 Construction of a Map from a Given Kneading Sequence 255
4.7.5 Rotation Interval and Well-Ordered Periodic Sequences 256
5 Symbolic Dynamics of Two-Dimensional Maps 258
5.1 General Discussion 260
5.1.1 Bi-Infinite Symbolic Sequences 261
5.1.2 Decomposition of the Phase Plane 263
5.1.3 Tangencies and Admissibility Conditions 264
5.1.4 Admissibility Conditions in Symbolic Plane 265
5.2 Invariant Manifolds and Dynamical Foliations of Phase Plane 268
5.2.1 Stable and Unstable Invariant Manifolds 268
5.2.2 Dynamical Foliations of the Phase Plane 272
5.2.3 Summary and Discussion 275
5.3 The Tél Map 276
5.3.1 Forward and Backward Symbolic Sequences 278
5.3.2 Dynamical Foliations of Phase Space and Their Ordering 279
5.3.3 Forbidden and Allowed Zones in Symbolic Plane 287
5.3.4 The Admissibility Conditions 290
5.3.5 Summary 294
5.4 The Lozi Map 295
5.4.1 Forward and Backward Symbolic Sequences 297
5.4.2 Dynamical Foliations of the Phase Space 298
5.4.3 Ordering of the Forward and Backward Foliations 307
5.4.4 Allowed and Forbidden Zones in the Symbolic Plane 309
5.4.5 Discussion of the Admissibility Condition 314
5.5 The Hénon Map 315
5.5.1 Fixed Points and Their Stability 317
5.5.2 Determination of Partition Lines in Phase Plane 320
5.5.3 Hénon-Type Symbolic Dynamics 325
5.5.4 Symbolic Analysis at Typical Parameter Values 328
5.5.5 Discussion 332
5.6 The Dissipative Standard Map 338
5.6.1 Dynamical Foliations of the Phase Plane 338
5.6.2 Ordering of Symbolic Sequences 341
5.6.3 Symbolic Plane and Admissibility of Symbolic Sequences 343
5.7 The Stadium Billiard Problem 347
5.7.1 A Coding Based on Lifting 349
5.7.2 Relation to Other Codings 352
5.7.3 The Half-Stadium 354
5.7.4 Summary 356
6 Application to Ordinary Differential Equations 357
6.1 General Discussion 359
6.1.1 Three Types of ODEs 359
6.1.2 On Numerical Integration of Differential Equations 361
6.1.3 Numerical Calculation of the Poincaré Maps 364
6.2 The Periodically Forced Brusselator 368
6.2.1 The Brusselator Viewed from The Standard Map 370
6.2.2 Transition from Annular to Interval Dynamics 376
6.2.3 Symbolic Analysis of Interval Dynamics 377
6.3 The Lorenz Equations 385
6.3.1 Summary of Known Properties 386
6.3.2 Construction of Poincaré and Return Maps 390
6.3.3 One-Dimensional Symbolic Dynamics Analysis 393
6.3.4 Symbolic Dynamics of the 2D Poincaré Maps 396
6.3.5 Stable Periodic Orbits 404
6.3.6 Concluding Remarks 413
6.4 Summary of Other ODE Systems 414
6.4.1 The Driven Two-Well Duffing Equation 414
6.4.2 The NMR-Laser Model 415
7 Counting the Number of Periodic Orbits 417
7.1 Periodic versus Chaotic Regimes 418
7.1.1 Stable Versus Unstable Periods in 1D Maps 419
7.1.2 Notations and Summary of Results 420
7.1.3 A Few Number Theory Notations and Functions 424
7.2 Number of Periodic Orbits in a Class of One-Parameter Maps 425
7.2.1 Number of Admissible Words in Symbolic Dynamics 426
7.2.2 Number of Tangent and Period-Doubling Bifurcations 427
7.2.3 Recursion Formula for the Total Number of Periods 429
7.2.4 Symmetry Types of Periodic Sequences 430
7.2.5 Explicit Solutions to the Recurrence Relations 435
7.2.6 Finite Lambda Auto-Expansion of Real Numbers 436
7.3 Other Aspects of the Counting Problem 438
7.3.1 The Number of Roots of the“Dark Line”Equation 438
7.3.2 Number of Saddle Nodes in Forming Smale Horseshoe 439
7.3.3 Number of Solutions of Renormalization Group Equations 439
7.4 Counting Formulae for General Continuous Maps 441
7.5 Number of Periods in Maps With Discontinuity 443
7.5.1 Number of Periods in the Gap Map 444
7.5.2 Number of Periods in the Lorenz-Like Map 446
7.6 Summary of the Counting Problem 447
7.7 Cycle Expansion for Topological Entropy 449
8 Symbolic Dynamics and Grammatical Complexity 453
8.1 Formal Languages and Their Complexity 455
8.1.1 Formal Language 455
8.1.2 Chomsky Hierarchy of Grammatical Complexity 456
8.1.3 The L-System 458
8.2 Regular Language and Finite Automaton 459
8.2.1 Finite Automaton 459
8.2.2 Regular Language 460
8.2.3 Stefan Matrix as Transfer Function for Automaton 461
8.3 Beyond Regular Languages 465
8.3.1 Feigenbaum and Generalized Feigenbaum Limiting Sets 466
8.3.2 Even and Odd Fibonacci Sequences 467
8.3.3 Odd Maximal Primitive Prefixes and Kneading Map 469
8.3.4 Even Maximal Primitive Prefixes and Distinct Excluded Blocks 472
8.4 Summary of Results 473
9 Symbolic Dynamics and Knot Theory 474
9.1 Knots and Links 475
9.2 Knots and Links from Unimodal Maps 477
9.3 Linking Numbers 481
9.4 Discussion 483
10 Appendix 485
A.1 Program to Generate Admissible Sequences 485
A.2 Program to Draw Dynamical Foliations of a Two-Dimensional Map 491
A.3 A Greedy Program for Determining Partition Line 496
References 499
R.1 Books 499
R.2 Papers 500
Index 517