Complexity of sequences and dynamical systems. (English) Zbl 0936.37008

The paper surveys results of recent papers on the combinatorial notion of symbolic complexity. In particular, the author gives a survey of an open question which is still very much in progress, namely, to determine which function can be the symbolic complexity function of a sequence. Also the links between the complexity of a sequence and its associated dynamical system are investigated and it is insisted on the cases where the knowledge of the complexity function allows to know either the sequence or at least the system. This leads to another open question, \(S\)-adic conjecture, and to a conceptual link with the notion of Kolmogorov-Chaitin complexity for infinite sequences, which is discussed.


37D45 Strange attractors, chaotic dynamics of systems with hyperbolic behavior
37B10 Symbolic dynamics
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI