# 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

## Access Full Article

top## Abstract

top## How to cite

topAvgustinovich, 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- J.-P. Allouche, The number of factors in a paperfolding sequence. Bull. Austral. Math. Soc.46 (1992) 23–32.
- J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity. Theoret. Comput. Sci.292 (2003) 9–31.
- 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.
- J. Berstel and P. Séébold, Sturmian words, in Algebraic combinatorics on words, edited by M. Lothaire. Cambridge University Press (2002).
- A.A. Bukhshtab, Number Theory. Uchpedgiz, Moscow (1960) (in Russian).
- J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67–88.
- J. Cassaigne and A. Frid, On arithmetical complexity of Sturmian words, in Proc. WORDS 2005, Montreal (2005) 197–208.
- J. Cassaigne and J. Karhumäki, Toeplitz words, generalized periodicity and periodically iterated morphisms. Eur. J. Combin. 18 (1997) 497–510.
- D. Damanik, Local symmetries in the period doubling sequence. Discrete Appl. Math.100 (2000) 115–121.
- S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math.206 (1999) 145–154.
- A. Frid, A lower bound for the arithmetical complexity of Sturmian words, Siberian Electronic Mathematical Reports 2, 14–22 [Russian, English abstract].
- A. Frid, Arithmetical complexity of symmetric D0L words. Theoret. Comput. Sci.306 (2003) 535–542.
- A. Frid, On Possible Growth of Arithmetical Complexity. RAIRO-Inf. Theor. Appl.40 (2006) 443–458.
- A. Frid, Sequences of linear arithmetical complexity. Theoret. Comput. Sci.339 (2005) 68–87.
- J. Justin and G. Pirillo, Decimations and Sturmian words. Theor. Inform. Appl.31 (1997) 271–290.
- T. Kamae and L. Zamboni, Maximal pattern complexity for discrete systems. Ergodic Theory Dynam. Syst.22 (2002) 1201–1214.
- M. Koskas, Complexités de suites de Toeplitz. Discrete Math.183 (1998) 161–183.
- 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.
- 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.
- E. Szemerédi, On sets of integers containing no k elements in arithmetic progression. Acta Arith. 27 (1975) 199–245.