staple
Avec cedram.org

Rechercher dans le site

Table des matières de ce fascicule | Article précédent | Article suivant
Théodore Tapsoba
Automates calculant la complexité de suites automatiques
Journal de théorie des nombres de Bordeaux, 6 no. 1 (1994), p. 127-134, doi: 10.5802/jtnb.109
Article PDF | Analyses MR 1305291 | Zbl 0815.11015

Résumé - Abstract

Le point fixe $u$ d’une substitution injective uniforme de module $\sigma $ sur un alphabet $A$ est examiné du point de vue du nombre $P(u, n)$ de ses blocs distincts de longueur $n$. Lorsque $u$ est minimal et $A$ de cardinal deux, nous construisons un automate pour la suite $n \rightarrow P(u, n +1) - P(u, n)$.

Bibliographie

[1] S. Arson, Démonstration de l'existence de suites asymitriques infinies, Mat. Sb. 44 (1937), 769-777.  Zbl 0018.11503 |  JFM 63.0928.01
[2] N. Bleuzen-Guernalec, Suites points fixes de transductions uniformes, C. R. Acad. Sci. Paris, Série I 300 (1985), 85-88.  MR 777740 |  Zbl 0578.68069
[3] S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math. 24 (1989), 83-96.  MR 1011264 |  Zbl 0683.20045
[4] 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
[5] A. Cobham, Uniform tag Sequences, Math. Systems Theory 6 (1972), 164-192.  MR 457011 |  Zbl 0253.02029
[6] W.H. Gottschalk and G.A. Hedlund, Topological dynamics, Am. Math. Soc. Colloq. Publ. 36, Providence R. I. (1968).  MR 74810 |  Zbl 0067.15204
[7] Lothaire, Combinatorics on words, Addison Wesley MA (1982), chapter 12.  Zbl 0514.20045
[8] A. de Luca and 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, Recurrent geodesic on a surface of negative curvate, Trans. Amer. Math. Soc. 22 (1921), 84-100.  MR 1501161 |  JFM 48.0786.06
[10] M. Queffélec, Contribution à l'étude spectrale de suites arithmétiques, Thèse d'État, Paris-Nord, (1984).
[11] G. Rauzy, Rotation sur les groupes, nombres algébriques et substitutions, Séminaire de Théorie des Nombres, Bordeaux, exposé 21 (1987- 1988), 21-1-21-12. Article |  Zbl 0726.11019
[12] T. Tapsoba, Complexité de suites automatiques, Thèse de troisième cycle, Université Aix-Marseille II (1987).
[13] A. Thue, Über unendliche Zeichenreihen, Norske Vid. Skr. I. Math. Kl., Christiana 7 (1906), 1-22.  JFM 37.0066.17
[14] A. Thue, Über die gegenseitige Lage gleicher Teile genvisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Math. Nat. Kl., Christiana 1 (1912), 1-67.  JFM 44.0462.01