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 : https://doi.org/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},
     zbl = {1110.68116},
     mrnumber = {2277050},
     language = {en},
     url = {http://www.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
DA  - 2006///
SP  - 569
EP  - 582
VL  - 40
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2006041/
UR  - https://zbmath.org/?q=an%3A1110.68116
UR  - https://www.ams.org/mathscinet-getitem?mr=2277050
UR  - https://doi.org/10.1051/ita:2006041
DO  - 10.1051/ita:2006041
LA  - en
ID  - ITA_2006__40_4_569_0
ER  - 
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://www.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 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]. | EuDML 53574 | 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. | EuDML 249690 | 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. | EuDML 92562 | 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. | EuDML 249073 | Numdam | MR 2142236 | Zbl 1155.68479

[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. | EuDML 205339 | MR 369312 | Zbl 0303.10056

Cité par Sources :