Complexity of sequences and dynamical systems (Q1304818)

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.