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.  
  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).  
  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.  
  8. J. Cassaigne and J. Karhumäki, Toeplitz words, generalized periodicity and periodically iterated morphisms. Eur. J. Combin. 18 (1997) 497–510.  
  9. D. Damanik, Local symmetries in the period doubling sequence. Discrete Appl. Math.100 (2000) 115–121.  
  10. S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math.206 (1999) 145–154.  
  11. A. Frid, A lower bound for the arithmetical complexity of Sturmian words, Siberian Electronic Mathematical Reports 2, 14–22 [Russian, English abstract].  
  12. A. Frid, Arithmetical complexity of symmetric D0L words. Theoret. Comput. Sci.306 (2003) 535–542.  
  13. A. Frid, On Possible Growth of Arithmetical Complexity. RAIRO-Inf. Theor. Appl.40 (2006) 443–458.  
  14. A. Frid, Sequences of linear arithmetical complexity. Theoret. Comput. Sci.339 (2005) 68–87.  
  15. J. Justin and G. Pirillo, Decimations and Sturmian words. Theor. Inform. Appl.31 (1997) 271–290.  
  16. T. Kamae and L. Zamboni, Maximal pattern complexity for discrete systems. Ergodic Theory Dynam. Syst.22 (2002) 1201–1214.  
  17. M. Koskas, Complexités de suites de Toeplitz. Discrete Math.183 (1998) 161–183.  
  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.  
  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.  
  20. E. Szemerédi, On sets of integers containing no k elements in arithmetic progression. Acta Arith. 27 (1975) 199–245.  

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.