Complexity

Abstract......Page 1
Series......Page 2
Title......Page 3
TITLES IN PRINT IN THIS SERIES......Page 4
Title page......Page 5
Copyright page......Page 6
Contents......Page 7
Preface......Page 11
Part 1 Phenomenology and models......Page 15
1.1 Statement of the problem......Page 17
1.2 Historical perspective......Page 21
1.3 Self-generated complexity......Page 23
2 Examples of complex behaviour......Page 26
2.1.1 Temporally "complex" dynamics......Page 27
2.1.2 Spatio-temporal "complexity"......Page 29
2.2 Turbulence......Page 31
2.3 Biological and chemical reactions......Page 33
2.4 Optical instabilities......Page 35
2.5 Growth phenomena......Page 37
2.6 DNA......Page 40
2.6.1 The genetic code......Page 41
2.6.2 Structure and function......Page 43
3 Mathematical models......Page 46
3.1 Reduction methods for partial differential equations......Page 47
3.2 Ordinary differential equations......Page 51
3.3 Mappings......Page 53
3.3.1 Strange attractors......Page 55
3.4 Cellular automata......Page 62
3.4.1 Regular rules......Page 65
3.4.3 "Complex" rules......Page 67
3.5 Statistical mechanical systems......Page 71
3.5.1 Spin glasses......Page 74
3.5.2 Optimization and artificial neural networks......Page 78
Part 2 Mathematical tools......Page 81
4 Symbolic representations of physical systems......Page 83
4.1 Encoding in nonlinear dynamics......Page 84
4.2 Shifts and invariant sets......Page 90
4.2.1 Shift dynamical systems......Page 91
4.3 Languages......Page 92
4.3.1 Topological entropy......Page 95
4.3.2 Substitutions......Page 96
5 Probability, ergodic theory, and information......Page 99
5.1 Measure-preserving transformations......Page 100
5.2 Stochastic processes......Page 103
5.3 Time-evolution operators......Page 107
5.4 Correlation functions......Page 110
5.5 Ergodic theory......Page 114
5.5.1 Spectral theory and isomorphism......Page 118
5.5.2 Shift dynamical systems......Page 119
5.5.3 What is the "generic" behaviour?......Page 121
5.5.4 Approximation theories......Page 122
5.6 Information, entropy, and dimension......Page 123
6.1 Interactions......Page 133
6.2.1 Generalized entropies......Page 137
6.2.2 Generalized dimensions......Page 142
6.3 Phase transitions......Page 146
6.3.1 Critical exponents, universality, and renormalization......Page 148
6.3.2 Disordered systems......Page 155
6.4.1 Power spectral measures and decay of correlation functions......Page 162
6.4.2 Thermodynamics of shift dynamical systems......Page 165
Part 3 Formal characterization of complexity......Page 177
7 Physical and computational analysis of symbolic signals......Page 179
7.1 Formal languages, grammars, and automata......Page 180
7.1.1 Regular languages......Page 181
7.1.2 Context-free languages......Page 184
7.1.3 Context-sensitive languages......Page 189
7.1.4 Unrestricted languages......Page 191
7.1.5 Other languages......Page 197
7.2.1 Regular languages......Page 198
7.2.2 Context-free languages......Page 201
7.2.3 DOL languages......Page 204
7.2.4 Context-sensitive and recursively enumerable languages......Page 211
7.3.1 Dynamics at the borderline with chaos......Page 212
7.3.2 Quasicrystals......Page 214
7.3.3 Chaotic maps......Page 216
7.3.4 Cellular automata......Page 217
7.3.5 Relationship between Turing machines and dynamical systems......Page 221
7.3.6 Nucleotide sequences......Page 223
7.3.7 Discussion......Page 225
8 Algorithmic and grammatical complexities......Page 227
8.1 Coding and data compression......Page 228
8.2 Model inference......Page 233
8.3 Algorithmic information......Page 240
8.3.1 P-NP problems......Page 244
8.4 Lempel-Ziv complexity......Page 247
8.5 Logical depth......Page 249
8.6 Sophistication......Page 251
8.7 Regular-language and set complexities......Page 254
8.8 Grammatical complexity......Page 257
9 Hierarchical scaling complexities......Page 262
9.1 Diversity of trees......Page 263
9.1.1 Horton-Strahler indices......Page 266
9.2 Effective-measure and forecasting complexity......Page 267
9.3 Topological exponents......Page 269
9.4.1 Global prediction......Page 274
9.4.2 Detailed prediction......Page 276
9.5 Scaling function......Page 284
10 Summary and perspectives......Page 291
Appendix 1 The Lorenz model......Page 295
Appendix 2 The horseshoe map......Page 297
Appendix 3 Mathematical definitions......Page 299
Appendix 4 Lyapunov exponents, entropy, and dimension......Page 301
Appendix 5 Forbidden words in regular languages......Page 304
References......Page 307
Index......Page 325