Sequences of low arithmetical complexity
Sobolev Institute of Mathematics SB RAS,
Koptyug Av. 4, Novosibirsk, Russia; firstname.lastname@example.org; email@example.com
2 Institut de Mathématiques de Luminy, case 907, 163 Av. de Luminy, 13288 Marseille Cedex 9, France; firstname.lastname@example.org
Accepted: 30 October 2003
Arithmetical complexity of a sequence is the number of words of length n that can be extracted from it according to arithmetic progressions. We study uniformly recurrent words of low arithmetical complexity and describe the family of such words having lowest complexity.
Mathematics Subject Classification: 68R15
Key words: Arithmetical complexity / infinite words / Toeplitz words / special factors / period doubling word / Legendre symbol / paperfolding word.
© EDP Sciences, 2006