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

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

Journal de théorie des nombres de Bordeaux (1993)

  • Volume: 5, Issue: 2, page 283-302
  • ISSN: 1246-7405

Abstract

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

How to cite

top

Allouche, J.-P., and Shallit, J. O.. "Complexité des suites de Rudin-Shapiro généralisées." Journal de théorie des nombres de Bordeaux 5.2 (1993): 283-302. <http://eudml.org/doc/93583>.

@article{Allouche1993,
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.},
author = {Allouche, J.-P., Shallit, J. O.},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {Rudin-Shapiro sequence; complexity; finite alphabet; automatic sequences; generalized Rudin- Shapiro sequence},
language = {fre},
number = {2},
pages = {283-302},
publisher = {Université Bordeaux I},
title = {Complexité des suites de Rudin-Shapiro généralisées},
url = {http://eudml.org/doc/93583},
volume = {5},
year = {1993},
}

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
PB - Université Bordeaux I
VL - 5
IS - 2
SP - 283
EP - 302
AB - 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.
LA - fre
KW - Rudin-Shapiro sequence; complexity; finite alphabet; automatic sequences; generalized Rudin- Shapiro sequence
UR - http://eudml.org/doc/93583
ER -

References

top
  1. [1] J.-P. Allouche et P. Liardet, Generalized Rudin-Shapiro sequences, Acta Arith.60 (1991), 1-27. Zbl0763.11010MR1129977
  2. [2] P. Arnoux et G. Rauzy, Représentation géométrique des suites de complexité 2n+1, Bull. Soc. math. France119 (1991), 199-215. Zbl0789.28011MR1116845
  3. [3] S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Appl. Math.24 (1989), 83-96. Zbl0683.20045MR1011264
  4. [4] S. Brlek, Communication privée. 
  5. [5] G. Christol, T. Kamae, M. Mendès France et G. Rauzy, Suites algébriques, automates et substitutions, Bull. Soc. math. France108 (1980), 401-419. Zbl0472.10035MR614317
  6. [6] A. Cobham, Uniform tag sequences, Math. Systems Theory6 (1972), 164-192. Zbl0253.02029MR457011
  7. [7] E.M. Coven et G.A. Hedlund, Sequences with minimal block growth, Math. Systems Theory7 (1973), 138-153. Zbl0256.54028MR322838
  8. [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. Zbl0671.10050MR993769
  9. [9] M. Morse et G.A. Hedlund, Symbolic Dynamics, II, Sturmian trajectories, Amer. J. Math. Soc.62 (1940), 1-42. Zbl0022.34003MR745JFM66.0188.03
  10. [10] J. Mouline, Contribution à l'étude de la complexité des suites substitutives, Thèse, Université de Provence, 1990. 
  11. [11] W. Rudin, Some theorems on Fourier coefficients, Proc. Amer. Math. Soc.10 (1959), 855-859. Zbl0091.05706MR116184
  12. [12] H.S. Shapiro, Extremal problems for polynomials and power series, M. S. Thesis, M. I. T., 1951. 
  13. [13] T. Tapsoba, Complexité de suites automatiques, Thèse de troisième cycle, Université Aix-Marseille II, 1987. 

NotesEmbed ?

top

You must be logged in to post comments.