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 = {https://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  - https://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 https://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. https://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

[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

  • Puzynina, Svetlana Complexity of Infinite Words, Machines, Computations, and Universality, Volume 15270 (2025), p. 1 | DOI:10.1007/978-3-031-81202-6_1
  • Aedo, Ibai; Grimm, Uwe; Mañibo, Neil; Nagai, Yasushi; Staynova, Petra Monochromatic arithmetic progressions in automatic sequences with group structure, Journal of Combinatorial Theory, Series A, Volume 203 (2024), p. 105831 | DOI:10.1016/j.jcta.2023.105831
  • Sobolewski, Bartosz On monochromatic arithmetic progressions in binary words associated with pattern sequences, Theoretical Computer Science, Volume 1018 (2024), p. 114815 | DOI:10.1016/j.tcs.2024.114815
  • Aedo, Ibai; Grimm, Uwe; Nagai, Yasushi; Staynova, Petra Monochromatic arithmetic progressions in binary Thue–Morse-like words, Theoretical Computer Science, Volume 934 (2022), p. 65 | DOI:10.1016/j.tcs.2022.08.013
  • Poláková, Miroslava Formulas for complexity, invariant measure and RQA characteristics of the period-doubling subshift, Communications in Nonlinear Science and Numerical Simulation, Volume 80 (2020), p. 104996 | DOI:10.1016/j.cnsns.2019.104996
  • Špitalský, Vladimír Recurrence Quantification Analysis of the Period-Doubling Sequence, International Journal of Bifurcation and Chaos, Volume 28 (2018) no. 14, p. 1850181 | DOI:10.1142/s021812741850181x
  • Parshina, Olga G. On Arithmetic Index in the Generalized Thue-Morse Word, Combinatorics on Words, Volume 10432 (2017), p. 121 | DOI:10.1007/978-3-319-66396-8_12
  • Bibliography, Formal Languages, Automata and Numeration Systems 1 (2014), p. 257 | DOI:10.1002/9781119008200.biblio
  • Bibliography, Formal Languages, Automata and Numeration Systems 2 (2014), p. 193 | DOI:10.1002/9781119042853.biblio
  • KAMAE, TETURO; SALIMOV, PAVEL V. On maximal pattern complexity of some automatic words, Ergodic Theory and Dynamical Systems, Volume 31 (2011) no. 5, p. 1463 | DOI:10.1017/s0143385710000453
  • Мучник, Андрей Альбертович; Muchnik, Andrei Albertovich; Притыкин, Юрий Львович; Pritykin, Yurii L'vovich; Семeнов, Алексей Львович; Semenov, Aleksei L'vovich Последовательности, близкие к периодическим, Успехи математических наук, Volume 64 (2009) no. 5, p. 21 | DOI:10.4213/rm9315
  • Berstel, Jean Sturmian and Episturmian Words, Algebraic Informatics, Volume 4728 (2007), p. 23 | DOI:10.1007/978-3-540-75414-5_2
  • Cassaigne, J.; Frid, A.E. On the arithmetical complexity of Sturmian words, Theoretical Computer Science, Volume 380 (2007) no. 3, p. 304 | DOI:10.1016/j.tcs.2007.03.022

Cité par 13 documents. Sources : Crossref