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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.