Arithmetical complexity of a sequence is the number of words of length 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.
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://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 SP - 569 EP - 582 VL - 40 IS - 4 PB - EDP-Sciences UR - http://www.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://www.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://www.numdam.org/articles/10.1051/ita:2006041/
[1] The number of factors in a paperfolding sequence. Bull. Austral. Math. Soc. 46 (1992) 23-32. | Zbl
,[2] Palindrome complexity. Theoret. Comput. Sci. 292 (2003) 9-31. | Zbl
, , and ,[3] 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.
, and ,[4] Sturmian words, in Algebraic combinatorics on words, edited by M. Lothaire. Cambridge University Press (2002). | MR
and ,[5] Number Theory. Uchpedgiz, Moscow (1960) (in Russian).
,[6] Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 67-88. | Zbl
,[7] On arithmetical complexity of Sturmian words, in Proc. WORDS 2005, Montreal (2005) 197-208.
and ,[8] Toeplitz words, generalized periodicity and periodically iterated morphisms. Eur. J. Combin. 18 (1997) 497-510. | Zbl
and ,[9] Local symmetries in the period doubling sequence. Discrete Appl. Math. 100 (2000) 115-121. | Zbl
,[10] Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145-154. | MR | Zbl
,[11] A lower bound for the arithmetical complexity of Sturmian words, Siberian Electronic Mathematical Reports 2, 14-22 [Russian, English abstract]. | EuDML | MR | Zbl
,[12] Arithmetical complexity of symmetric D0L words. Theoret. Comput. Sci. 306 (2003) 535-542. | MR | Zbl
,[13] On Possible Growth of Arithmetical Complexity. RAIRO-Inf. Theor. Appl. 40 (2006) 443-458. | EuDML | Numdam | Zbl
,[14] Sequences of linear arithmetical complexity. Theoret. Comput. Sci. 339 (2005) 68-87. | MR | Zbl
,[15] Decimations and Sturmian words. Theor. Inform. Appl. 31 (1997) 271-290. | EuDML | Numdam | MR | Zbl
and ,[16] Maximal pattern complexity for discrete systems. Ergodic Theory Dynam. Syst. 22 (2002) 1201-1214. | MR | Zbl
and ,[17] Complexités de suites de Toeplitz. Discrete Math. 183 (1998) 161-183. | MR | Zbl
,[18] EuDML | Numdam | MR | Zbl
, , , , and , *-Sturmian words and complexity. J. Théor. Nombres Bordeaux 15 (2003) 767-804. |[19] 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
and ,[20] On sets of integers containing no elements in arithmetic progression. Acta Arith. 27 (1975) 199-245. | EuDML | MR | Zbl
,Cité par Sources :