Geodesic
A~lower bound for the arithmetical complexity of Sturmian words
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 2 (2005), pp. 14-22.

Voir la notice de l'article provenant de la source Math-Net.Ru

We give an $O(n^3)$ lower bound for the arithmetical complexity of a Sturmian word, that is the number of words of length $n$ occuring in all arithmetic progressions of a Sturmian word. This result supplements the recent $O(n^3)$ upper bound for the same function by Cassaigne and Frid. 
@article{SEMR_2005_2_a1,
     author = {A. \`E. Frid},
     title = {A~lower bound for the arithmetical complexity of {Sturmian} words},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {14--22},
     publisher = {mathdoc},
     volume = {2},
     year = {2005},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2005_2_a1/}
}
TY  - JOUR
AU  - A. È. Frid
TI  - A~lower bound for the arithmetical complexity of Sturmian words
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2005
SP  - 14
EP  - 22
VL  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2005_2_a1/
LA  - ru
ID  - SEMR_2005_2_a1
ER  - 
%0 Journal Article
%A A. È. Frid
%T A~lower bound for the arithmetical complexity of Sturmian words
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2005
%P 14-22
%V 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2005_2_a1/
%G ru
%F SEMR_2005_2_a1
A. È. Frid. A~lower bound for the arithmetical complexity of Sturmian words. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 2 (2005), pp. 14-22. http://geodesic.mathdoc.fr/item/SEMR_2005_2_a1/

[1] S. V. Avgustinovich, D. G. Fon-Der-Flaass, A. E. Frid, “Arithmetical complexity of infinite words”, Words, Languages and Combinatorics III, Proc. 3rd ICWLC, Kyoto, March 2000, World Scientific, Singapore, 2003, 51–62 | MR

[2] J. Berstel, D. Perrin, “Finite and infinite words”: M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002, 1–39 | MR

[3] J. Berstel, P. Séébold, “Sturmian words”: M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002, 40–97 | MR

[4] J. Cassaigne, A. Frid, On arithmetical complexity of Sturmian words (to appear)

[5] E. M. Coven, G. A. Hedlund, “Sequences with minimal block growth”, Math. Systems Theory, 7 (2003), 138–153 | DOI | MR

[6] N. J. Fine and H. S. Wilf, “Uniqueness theorem for periodic functions”, Proc. Amer. Math. Soc., 16 (1965), 109–114 | MR | Zbl

[7] A. Frid, “Arithmetical complexity of symmetric D0L words”, Theoret. Comput. Sci., 306 (2003), 535–542 | DOI | MR | Zbl

[8] A. Frid, On possible growth of arithmetical complexity, http://www.math.nsc.ru/LBRT/k4/Frid/frid_for_ita.ps

[9] A. Frid, “Sequences of linear arithmetical complexity”, Theoret. Comput. Sci. (to appear) | MR

[10] T. Kamae, L. Zamboni, “Sequence entropy and the maximal pattern complexity of infinite words”, Ergodic Theory Dynam. Systems, 22 (2002), 1191–1199 | MR | Zbl

[11] F. Mignosi, A. Restivo, “Periodicity”: M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002, 237–274 | MR

[12] G. Rote, “Sequences with subword complexity $2n$”, J. Number Th., 46 (1994), 196–213 | DOI | MR | Zbl

[13] L. Vuillon, “A characterisation of Sturmian words by return words”, European Journal of Combinatorics, 22 (2001), 263–275 | DOI | MR | Zbl