Complexité des suites de Rudin-Shapiro généralisées
Journal de théorie des nombres de Bordeaux, Volume 5 (1993) no. 2, p. 283-302

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.

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.

Keywords: Rudin-Shapiro sequence, complexity
@article{JTNB_1993__5_2_283_0,
     author = {Allouche, Jean-Paul and Shallit, Jeffrey O.},
     title = {Complexit\'e des suites de Rudin-Shapiro g\'en\'eralis\'ees},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux I},
     volume = {5},
     number = {2},
     year = {1993},
     pages = {283-302},
     zbl = {0817.11014},
     mrnumber = {1265906},
     language = {fr},
     url = {http://www.numdam.org/item/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, Volume 5 (1993) no. 2, pp. 283-302. http://www.numdam.org/item/JTNB_1993__5_2_283_0/

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

[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 1116845 | Zbl 0789.28011

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

[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 614317 | Zbl 0472.10035

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

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

[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 993769 | Zbl 0671.10050

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

[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 116184 | Zbl 0091.05706

[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.