Sequences of low arithmetical complexity
Avgustinovich, Sergey V. ; Cassaigne, Julien ; Frid, Anna E.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006), p. 569-582 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2006-01-01
DOI : https://doi.org/10.1051/ita:2006041
Classification:  68R15 
@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},
     volume = {40},
     year = {2006},
     pages = {569-582},
     doi = {10.1051/ita:2006041},
     mrnumber = {2277050},
     zbl = {1110.68116},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 569-582. doi : 10.1051/ita:2006041. http://gdmltest.u-ga.fr/item/ITA_2006__40_4_569_0/

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

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

[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 1905123

[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 0921.68065

[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 0881.68065

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

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

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

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

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

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

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

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

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

[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. | Numdam | MR 2142236 | Zbl 1155.68479 | Zbl pre02184624

[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 2033906 | Zbl 1060.68098

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