Sequences with subword complexity \(2n\) (Q1320503)

The complexity of an infinite sequence taking finitely many values is the function \(n \to P(n)\), where \(P(n)\) is the number of blocks of length \(n\) occurring in the sequence (the usual term for ``blocks'' is ``factors'' in the European terminology and ``subwords'' in the American terminology). One can be interested in the asymptotic behaviour of \(P(n)\), or in explicit computations, in particular one can study the sequences having ``simple'' complexity functions. A survey on the complexity is given by the reviewer in Bull. Belg. Math. Soc. -- Simon Stevin 1, No. 2, 133-143 (1994)]. In the paper under review the author studies infinite sequences for which \(P(n) = 2n\). This case is intermediate between the Sturmian (or billiard) sequences (of complexity \(n + 1)\) and the Arnoux-Rauzy sequences (of complexity \(2n + 1)\). The author gives a class of \(2n\)-sequences related to the Sturmian sequences (hence with a geometrical interpretation), indeed the \(2n\)- sequences closed under complementation. He also gives other examples of \(2n\)-sequences, which are generated by substitutions. The author announces that his method, based on ``graphs of words'' (also known as Rauzy's graphs) should permit to study all sequences of complexity \(2n\), as well as the sequences of complexity \(2n+k\).