Complexité des suites de Rudin-Shapiro généralisées

Allouche, J.-P.; Shallit, J. O.

Allouche, J.-P. ; Shallit, J. O.

Journal de théorie des nombres de Bordeaux, Tome 5 (1993) no. 2, pp. 283-302.

Résumé
Abstract

La complexité d’une suite infinie est définie comme la fonction qui compte le nombre de facteurs de longueur $k$ dans cette suite. Nous prouvons ici que la complexité des suites de Rudin-Shapiro généralisées (qui comptent les occurrences de certains facteurs dans les développements binaires d’entiers) est ultimement affine.

The complexity of an infinite sequence is defined as the function counting the number of factors of length $k$ in this sequence. We consider the generalized Rudin-Shapiro sequences, which count the number of occurrences of a certain type of blocks in the binary expansion of the nonegative integers, and we prove that their complexity function is an ultimately affine function.

MR Zbl

Mots clés : Rudin-Shapiro sequence, complexity

@article{JTNB_1993__5_2_283_0,
     author = {Allouche, J.-P. and Shallit, J. O.},
     title = {Complexit\'e des suites de {Rudin-Shapiro} g\'en\'eralis\'ees},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {283--302},
     publisher = {Universit\'e Bordeaux I},
     volume = {5},
     number = {2},
     year = {1993},
     mrnumber = {1265906},
     zbl = {0817.11014},
     language = {fr},
     url = {http://www.numdam.org/item/JTNB_1993__5_2_283_0/}
}

TY  - JOUR
AU  - Allouche, J.-P.
AU  - Shallit, J. O.
TI  - Complexité des suites de Rudin-Shapiro généralisées
JO  - Journal de théorie des nombres de Bordeaux
PY  - 1993
SP  - 283
EP  - 302
VL  - 5
IS  - 2
PB  - Université Bordeaux I
UR  - http://www.numdam.org/item/JTNB_1993__5_2_283_0/
LA  - fr
ID  - JTNB_1993__5_2_283_0
ER  -

%0 Journal Article
%A Allouche, J.-P.
%A Shallit, J. O.
%T Complexité des suites de Rudin-Shapiro généralisées
%J Journal de théorie des nombres de Bordeaux
%D 1993
%P 283-302
%V 5
%N 2
%I Université Bordeaux I
%U http://www.numdam.org/item/JTNB_1993__5_2_283_0/
%G fr
%F JTNB_1993__5_2_283_0

Allouche, J.-P.; Shallit, J. O. Complexité des suites de Rudin-Shapiro généralisées. Journal de théorie des nombres de Bordeaux, Tome 5 (1993) no. 2, pp. 283-302. http://www.numdam.org/item/JTNB_1993__5_2_283_0/

Bibliographie
Cité par

[1] J.-P. Allouche et P. Liardet, Generalized Rudin-Shapiro sequences, Acta Arith. 60 (1991), 1-27. | MR | Zbl

[2] P. Arnoux et G. Rauzy, Représentation géométrique des suites de complexité 2n+1, Bull. Soc. math. France 119 (1991), 199-215. | Numdam | MR | Zbl

[3] S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Appl. Math. 24 (1989), 83-96. | MR | Zbl

[4] S. Brlek, Communication privée.

[5] G. Christol, T. Kamae, M. Mendès France et G. Rauzy, Suites algébriques, automates et substitutions, Bull. Soc. math. France 108 (1980), 401-419. | Numdam | MR | Zbl

[6] A. Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972), 164-192. | MR | Zbl

[7] E.M. Coven et G.A. Hedlund, Sequences with minimal block growth, Math. Systems Theory 7 (1973), 138-153. | MR | Zbl

[8] A. De Luca et S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Theoret. Comput. Sci. 63 (1989), 333-348. | MR | Zbl

[9] M. Morse et G.A. Hedlund, Symbolic Dynamics, II, Sturmian trajectories, Amer. J. Math. Soc. 62 (1940), 1-42. | JFM | MR | Zbl

[10] J. Mouline, Contribution à l'étude de la complexité des suites substitutives, Thèse, Université de Provence, 1990.

[11] W. Rudin, Some theorems on Fourier coefficients, Proc. Amer. Math. Soc. 10 (1959), 855-859. | MR | Zbl

[12] H.S. Shapiro, Extremal problems for polynomials and power series, M. S. Thesis, M. I. T., 1951.

[13] T. Tapsoba, Complexité de suites automatiques, Thèse de troisième cycle, Université Aix-Marseille II, 1987.