Cover

Half-title

Title

Copyright

Contents

Preface

Part I Phenomenology and models

Chapter 1 Introduction

1.1 Statement of the problem

1.2 Historical perspective

1.3 Self-generated complexity

Chapter 2 Examples of complex behaviour

2.1 Instabilities in fluids

2.1.1 Temporally "complex" dynamics

2.1.2 Spatio-temporal "complexity"

2.2 Turbulence

2.3 Biological and chemical reactions

2.4 Optical instabilities

2.5 Growth phenomena

2.6 DNA

2.6.1 The genetic code

2.6.2 Structure and function

Chapter 3 Mathematical models

3.1 Reduction methods for partial differential equations

3.2 Ordinary differential equations

3.3 Mappings

3.3.1 Strange attractors

3.4 Cellular automata

3.4.1 Regular rules

3.4.2 Chaotic rules

3.4.3 "Complex" rules

3.5 Statistical mechanical systems

3.5.1 Spin glasses

3.5.2 Optimization and artificial neural networks

Part 2 Mathematical tools

Chapter 4 Symbolic representations of physical systems

4.1 Encoding in nonlinear dynamics

4.2 Shifts and invariant sets

4.2.1 Shift dynamical systems

4.3 Languages

4.3.1 Topological entropy

4.3.2 Substitutions

Chapter 5 Probability, ergodic theory, and information

5.1 Measure-preserving transformations

5.2 Stochastic processes

5.3 Time-evolution operators

5.4 Correlation functions

5.5 Ergodic theory

5.5.1 Spectral theory and isomorphism

5.5.2 Shift dynamical systems

5-5-3 What is the "generic" behaviour?

5.5.4 Approximation theories

5.6 Information, entropy, and dimension

Chapter 6 Thermodynamic formalism

6.1 Interactions

6.2 Statistical ensembles

6.2.1 Generalized entropies

6.2.2 Generalized dimensions

6.3 Phase transitions

6.3.1 Critical exponents, universality, and renormalization

6.3.2 Disordered systems

6.4 Applications

6.4.1 Power spectral measures and decay of correlation functions

6.4.2 Thermodynamics of shift dynamical systems

Part 3 Formal characterization of complexity

Chapter 7 Physical and computational analysis of symbolic signals

7.1 Formal languages, grammars, and automata

7.1.1 Regular languages

7.1.2 Context-free languages

7.1.3 Context-sensitive languages

7.1.4 Unrestricted languages

7.1.5 Other languages

7.2 Physical characterization of formal languages

7.2.1 Regular languages

7.2.2 Context-free languages

7.2.3 DOL languages

7.2.4 Context-sensitive and recursively enumerable languages

7.3 Computational characterization of physical systems and mathematical models

7.3.1 Dynamics at the borderline with chaos

7.3.2 Quasicrystals

7.3.3 Chaotic maps

7.3.4 Cellular automata

7.3.5 Relationship between Turing machines and dynamical systems

7.3.6 Nucleotide sequences

7.3.7 Discussion

Chapter 8 Algorithmic and grammatical complexities

8.1 Coding and data compression

8.2 Model inference

8.3 Algorithmic information

8.3.1 P-NP problems

8.4 Lempel-Ziv complexity

8.5 Logical depth

8.6 Sophistication

8.7 Regular-language and set complexities

8.8 Grammatical complexity

Chapter 9 Hierarchical scaling complexities

9.1 Diversity of trees

9.1.1 Horton-Strahler indices

9.2 Effective-measure and forecasting complexity

9.3 Topological exponents

9.4 Convergence of model predictions

9.4.1 Global prediction

9.4.2 Detailed prediction

9.5 Scaling function

Chapter 10 Summary and perspectives

Appendix 1 The Lorenz model

Appendix 2 The horseshoe map

Appendix 3 Mathematical definitions

Appendix 4 Lyapunov exponents, entropy, and dimension

Appendix 5 Forbidden words in regular languages

References

Index