Sequences of low arithmetical complexity

Sergey V. Avgustinovich; Julien Cassaigne; Anna E. Frid

RAIRO - Theoretical Informatics and Applications (2006)

  • Volume: 40, Issue: 4, page 569-582
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Avgustinovich, Sergey V., Cassaigne, Julien, and Frid, Anna E.. "Sequences of low arithmetical complexity." RAIRO - Theoretical Informatics and Applications 40.4 (2006): 569-582. <http://eudml.org/doc/249693>.

@article{Avgustinovich2006,
abstract = { 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. },
author = {Avgustinovich, Sergey V., Cassaigne, Julien, Frid, Anna E.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Arithmetical complexity; infinite words; Toeplitz words; special factors; period doubling word; Legendre symbol; paperfolding word.; arithmetical complexity; special factors; paperfolding word},
language = {eng},
month = {11},
number = {4},
pages = {569-582},
publisher = {EDP Sciences},
title = {Sequences of low arithmetical complexity},
url = {http://eudml.org/doc/249693},
volume = {40},
year = {2006},
}

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
DA - 2006/11//
PB - EDP Sciences
VL - 40
IS - 4
SP - 569
EP - 582
AB - 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.
LA - eng
KW - Arithmetical complexity; infinite words; Toeplitz words; special factors; period doubling word; Legendre symbol; paperfolding word.; arithmetical complexity; special factors; paperfolding word
UR - http://eudml.org/doc/249693
ER -

References

top
  1. J.-P. Allouche, The number of factors in a paperfolding sequence. Bull. Austral. Math. Soc.46 (1992) 23–32.  Zbl0753.11011
  2. J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity. Theoret. Comput. Sci.292 (2003) 9–31.  
  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).  Zbl0883.68104
  5. A.A. Bukhshtab, Number Theory. Uchpedgiz, Moscow (1960) (in Russian).  
  6. J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67–88.  
  7. J. Cassaigne and A. Frid, On arithmetical complexity of Sturmian words, in Proc. WORDS 2005, Montreal (2005) 197–208.  Zbl1119.68138
  8. J. Cassaigne and J. Karhumäki, Toeplitz words, generalized periodicity and periodically iterated morphisms. Eur. J. Combin. 18 (1997) 497–510.  Zbl0881.68065
  9. D. Damanik, Local symmetries in the period doubling sequence. Discrete Appl. Math.100 (2000) 115–121.  Zbl0943.68127
  10. S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math.206 (1999) 145–154.  Zbl0936.37008
  11. A. Frid, A lower bound for the arithmetical complexity of Sturmian words, Siberian Electronic Mathematical Reports 2, 14–22 [Russian, English abstract].  Zbl1125.68091
  12. A. Frid, Arithmetical complexity of symmetric D0L words. Theoret. Comput. Sci.306 (2003) 535–542.  Zbl1070.68068
  13. A. Frid, On Possible Growth of Arithmetical Complexity. RAIRO-Inf. Theor. Appl.40 (2006) 443–458.  Zbl1110.68120
  14. A. Frid, Sequences of linear arithmetical complexity. Theoret. Comput. Sci.339 (2005) 68–87.  Zbl1076.68053
  15. J. Justin and G. Pirillo, Decimations and Sturmian words. Theor. Inform. Appl.31 (1997) 271–290.  Zbl0889.68090
  16. T. Kamae and L. Zamboni, Maximal pattern complexity for discrete systems. Ergodic Theory Dynam. Syst.22 (2002) 1201–1214.  Zbl1014.37003
  17. M. Koskas, Complexités de suites de Toeplitz. Discrete Math.183 (1998) 161–183.  Zbl0895.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 Bordeaux15 (2003) 767–804.  Zbl1155.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.  Zbl1060.68098
  20. E. Szemerédi, On sets of integers containing no k elements in arithmetic progression. Acta Arith. 27 (1975) 199–245.  Zbl0303.10056

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.