Sequences of low arithmetical complexity
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 569-582.

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.

DOI : 10.1051/ita:2006041
Classification : 68R15
Mots-clés : arithmetical complexity, infinite words, Toeplitz words, special factors, period doubling word, Legendre symbol, paperfolding word 
@article{ITA_2006__40_4_569_0,
     author = {Avgustinovich, Sergey V. and Cassaigne, Julien and Frid, Anna E.},
     title = {Sequences of low arithmetical complexity},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {569--582},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {4},
     year = {2006},
     doi = {10.1051/ita:2006041},
     mrnumber = {2277050},
     zbl = {1110.68116},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2006041/}
}
TY  - JOUR
AU  - Avgustinovich, Sergey V.
AU  - Cassaigne, Julien
AU  - Frid, Anna E.
TI  - Sequences of low arithmetical complexity
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
SP  - 569
EP  - 582
VL  - 40
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2006041/
DO  - 10.1051/ita:2006041
LA  - en
ID  - ITA_2006__40_4_569_0
ER  - 
%0 Journal Article
%A Avgustinovich, Sergey V.
%A Cassaigne, Julien
%A Frid, Anna E.
%T Sequences of low arithmetical complexity
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 569-582
%V 40
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2006041/
%R 10.1051/ita:2006041
%G en
%F ITA_2006__40_4_569_0
Avgustinovich, Sergey V.; Cassaigne, Julien; Frid, Anna E. Sequences of low arithmetical complexity. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 569-582. doi : 10.1051/ita:2006041. http://archive.numdam.org/articles/10.1051/ita:2006041/

[1] J.-P. Allouche, The number of factors in a paperfolding sequence. Bull. Austral. Math. Soc. 46 (1992) 23-32. | Zbl

[2] J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity. Theoret. Comput. Sci. 292 (2003) 9-31. | Zbl

[3] S.V. Avgustinovich, D.G. Fon-Der-Flaass and A.E. Frid, Arithmetical complexity of infinite words, in Words, Languages & Combinatorics III, edited by M. Ito and T. Imaoka. Singapore, World Scientific Publishing, ICWLC 2000, Kyoto, Japan, March 14-18 (2003) 51-62.

[4] J. Berstel and P. Séébold, Sturmian words, in Algebraic combinatorics on words, edited by M. Lothaire. Cambridge University Press (2002). | MR

[5] A.A. Bukhshtab, Number Theory. Uchpedgiz, Moscow (1960) (in Russian).

[6] J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 67-88. | Zbl

[7] J. Cassaigne and A. Frid, On arithmetical complexity of Sturmian words, in Proc. WORDS 2005, Montreal (2005) 197-208.

[8] J. Cassaigne and J. Karhumäki, Toeplitz words, generalized periodicity and periodically iterated morphisms. Eur. J. Combin. 18 (1997) 497-510. | Zbl

[9] D. Damanik, Local symmetries in the period doubling sequence. Discrete Appl. Math. 100 (2000) 115-121. | Zbl

[10] S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145-154. | MR | Zbl

[11] A. Frid, A lower bound for the arithmetical complexity of Sturmian words, Siberian Electronic Mathematical Reports 2, 14-22 [Russian, English abstract]. | EuDML | MR | Zbl

[12] A. Frid, Arithmetical complexity of symmetric D0L words. Theoret. Comput. Sci. 306 (2003) 535-542. | MR | Zbl

[13] A. Frid, On Possible Growth of Arithmetical Complexity. RAIRO-Inf. Theor. Appl. 40 (2006) 443-458. | EuDML | Numdam | Zbl

[14] A. Frid, Sequences of linear arithmetical complexity. Theoret. Comput. Sci. 339 (2005) 68-87. | MR | Zbl

[15] J. Justin and G. Pirillo, Decimations and Sturmian words. Theor. Inform. Appl. 31 (1997) 271-290. | EuDML | Numdam | MR | Zbl

[16] T. Kamae and L. Zamboni, Maximal pattern complexity for discrete systems. Ergodic Theory Dynam. Syst. 22 (2002) 1201-1214. | MR | Zbl

[17] M. Koskas, Complexités de suites de Toeplitz. Discrete Math. 183 (1998) 161-183. | MR | Zbl

[18] I. Nakashima, J. Tamura, S. Yasutomi, I. Nakashima, J.-I. Tamura and S.-I. Yasutomi, *-Sturmian words and complexity. J. Théor. Nombres Bordeaux 15 (2003) 767-804. | EuDML | Numdam | MR | Zbl

[19] A. Restivo and S. Salemi, Binary patterns in infinite binary words, in Formal and Natural Computing, edited by W. Brauer et al. Lect. Notes Comput. Sci. 2300, (2002) 107-116. | MR | Zbl

[20] E. Szemerédi, On sets of integers containing no k elements in arithmetic progression. Acta Arith. 27 (1975) 199-245. | EuDML | MR | Zbl

Cité par Sources :