On possible growths of arithmetical complexity

Anna E. Frid

RAIRO - Theoretical Informatics and Applications (2006)

  • Volume: 40, Issue: 3, page 443-458
  • ISSN: 0988-3754

Abstract

top
The arithmetical complexity of infinite words, defined by Avgustinovich, Fon-Der-Flaass and the author in 2000, is the number of words of length n which occur in the arithmetical subsequences of the infinite word. This is one of the modifications of the classical function of subword complexity, which is equal to the number of factors of the infinite word of length n. In this paper, we show that the orders of growth of the arithmetical complexity can behave as many sub-polynomial functions. More precisely, for each sequence u of subword complexity ƒu(n) and for each prime p ≥ 3 we build a Toeplitz word on the same alphabet whose arithmetical complexity is a ( n ) = Θ ( n f u ( log p n ) ) .

How to cite

top

Frid, Anna E.. "On possible growths of arithmetical complexity." RAIRO - Theoretical Informatics and Applications 40.3 (2006): 443-458. <http://eudml.org/doc/249690>.

@article{Frid2006,
abstract = { The arithmetical complexity of infinite words, defined by Avgustinovich, Fon-Der-Flaass and the author in 2000, is the number of words of length n which occur in the arithmetical subsequences of the infinite word. This is one of the modifications of the classical function of subword complexity, which is equal to the number of factors of the infinite word of length n. In this paper, we show that the orders of growth of the arithmetical complexity can behave as many sub-polynomial functions. More precisely, for each sequence u of subword complexity ƒu(n) and for each prime p ≥ 3 we build a Toeplitz word on the same alphabet whose arithmetical complexity is $a(n)=\Theta(n f_u(\lceil \log_p n \rceil))$. },
author = {Frid, Anna E.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Arithmetical complexity; infinite word; subword complexity; Toeplitz word; bispecial words.; arithmetical complexity; bispecial words},
language = {eng},
month = {10},
number = {3},
pages = {443-458},
publisher = {EDP Sciences},
title = {On possible growths of arithmetical complexity},
url = {http://eudml.org/doc/249690},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Frid, Anna E.
TI - On possible growths of arithmetical complexity
JO - RAIRO - Theoretical Informatics and Applications
DA - 2006/10//
PB - EDP Sciences
VL - 40
IS - 3
SP - 443
EP - 458
AB - The arithmetical complexity of infinite words, defined by Avgustinovich, Fon-Der-Flaass and the author in 2000, is the number of words of length n which occur in the arithmetical subsequences of the infinite word. This is one of the modifications of the classical function of subword complexity, which is equal to the number of factors of the infinite word of length n. In this paper, we show that the orders of growth of the arithmetical complexity can behave as many sub-polynomial functions. More precisely, for each sequence u of subword complexity ƒu(n) and for each prime p ≥ 3 we build a Toeplitz word on the same alphabet whose arithmetical complexity is $a(n)=\Theta(n f_u(\lceil \log_p n \rceil))$.
LA - eng
KW - Arithmetical complexity; infinite word; subword complexity; Toeplitz word; bispecial words.; arithmetical complexity; bispecial words
UR - http://eudml.org/doc/249690
ER -

References

top
  1. J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity. Theoret. Comput. Sci.292 (2003) 9–31.  
  2. J.-P. Allouche and M. Bousquet-Mélou, Canonical positions for the factors in paperfolding sequences. Theoret. Comput. Sci.129 (1994) 263–278.  Zbl0820.11011
  3. J.-P. Allouche and J. Shallit, Automatic sequences: theory, applications, generalizations. Cambridge Univ. Press (2003).  Zbl1086.11015
  4. S.V. Avgustinovich, J. Cassaigne and A.E. Frid, Sequences of low arithmetical complexity. submitted.  Zbl1110.68116
  5. S.V. Avgustinovich, D.G. Fon-Der-Flaass and A.E. Frid, Arithmetical complexity of infinite words, in Words, Languages & Combinatorics III, Words, Languages & Combinatorics III, Singapore (2003), 51–62 World Scientific Publishing. ICWLC 2000, Kyoto, Japan, March (2000) 14–18.  
  6. J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67–88.  
  7. J. Cassaigne, Constructing infinite words of intermediate complexity, in Developments in Language Theory VI, edited by M. Ito and M. Toyama. Lect. Notes Comput. Sci.2450 (2003) 173–184.  Zbl1015.68138
  8. J. Cassaigne and A. Frid, On arithmetical complexity of Sturmian words, accepted to WORDS'05.  Zbl1119.68138
  9. J. Cassaigne and J. Karhumäki, Toeplitz words, generalized periodicity and periodically iterated morphisms. Eur. J. Combin.18 (1997) 497–510.  Zbl0881.68065
  10. D. Damanik, Local symmetries in the period doubling sequence. Discrete Appl. Math.100 (2000) 115–121.  Zbl0943.68127
  11. A. Iványi, On the d-complexity of words, Ann. Univ. Sci. Budapest. Sect. Comput.8 (1987) 69–90.  Zbl0663.68085
  12. S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math.206 (1999) 145–154.  Zbl0936.37008
  13. A. Frid, A lower bound for arithmetical complexity of Sturmian words. Siberian Electronic Math. Reports2 (2005) 14–22.  Zbl1125.68091
  14. A. Frid, Arithmetical complexity of symmetric D0L words. Theoret. Comput. Sci.306 (2003) 535–542.  Zbl1070.68068
  15. A. Frid, Sequences of linear arithmetical complexity. Theoret. Comput. Sci.339 (2005) 68–87.  Zbl1076.68053
  16. T. Kamae and L. Zamboni, Sequence entropy and the maximal pattern complexity of infinite words. Ergodic Theory Dynam. Syst.22 (2002) 1191–1199.  Zbl1014.37004
  17. T. Kamae and L. Zamboni, Maximal pattern complexity for discrete systems. Ergodic Theory Dynam. Syst.22 (2002), 1201–1214.  Zbl1014.37003
  18. T. Kamae and H. Rao, Maximal pattern complexity over l letters. Eur. J. Combin., to appear.  Zbl1082.68090
  19. T. Kamae and Y.-M. Xue, Two dimensional word with 2k maximal pattern complexity. Osaka J. Math.41 (2004) 257–265.  Zbl1053.37004
  20. M. Koskas, Complexités de suites de Toeplitz. Discrete Math.183 (1998) 161–183.  Zbl0895.11011
  21. I. Nakashima, J. Tamura and S. Yasutomi, Modified complexity and *-Sturmian words. Proc. Japan Acad. Ser. A75 (1999) 26–28.  Zbl0928.11012
  22. I. Nakashima, J.-I. Tamura and S.-I. Yasutomi, *-Sturmian words and complexity. J. Théorie des Nombres de Bordeaux15 (2003) 767–804.  Zbl1155.68479
  23. J.-E. Pin, Van der Waerden's theorem, in Combinatorics on words, edited by M. Lothaire. Addison-Wesley (1983) 39–54.  
  24. 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
  25. B.L. Van der Waerden, Beweis einer Baudet'schen Vermutung. Nieuw. Arch. Wisk.15 (1927) 212–216.  Zbl53.0073.12

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.