Automates calculant la complexité de suites automatiques
Journal de Théorie des Nombres de Bordeaux, Volume 6 (1994) no. 1, pp. 127-134.

A fixed point u of an injective substitution of constant length σ on an alphabet A is considered in relation with the number P(u,n) of its distinct n-blocks. When u is minimal and A a set of two elements, we prove that the sequence nP(u,n+1)-P(u,n) is obtained by an automaton which is built explicitly.

Le point fixe u d’une substitution injective uniforme de module σ 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 nP(u,n+1)-P(u,n).

@article{JTNB_1994__6_1_127_0,
     author = {Th\'eodore Tapsoba},
     title = {Automates calculant la complexit\'e de suites automatiques},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {127--134},
     publisher = {Universit\'e Bordeaux I},
     volume = {6},
     number = {1},
     year = {1994},
     doi = {10.5802/jtnb.109},
     zbl = {0815.11015},
     mrnumber = {1305291},
     language = {fr},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.109/}
}
TY  - JOUR
TI  - Automates calculant la complexité de suites automatiques
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 1994
DA  - 1994///
SP  - 127
EP  - 134
VL  - 6
IS  - 1
PB  - Université Bordeaux I
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.109/
UR  - https://zbmath.org/?q=an%3A0815.11015
UR  - https://www.ams.org/mathscinet-getitem?mr=1305291
UR  - https://doi.org/10.5802/jtnb.109
DO  - 10.5802/jtnb.109
LA  - fr
ID  - JTNB_1994__6_1_127_0
ER  - 
%0 Journal Article
%T Automates calculant la complexité de suites automatiques
%J Journal de Théorie des Nombres de Bordeaux
%D 1994
%P 127-134
%V 6
%N 1
%I Université Bordeaux I
%U https://doi.org/10.5802/jtnb.109
%R 10.5802/jtnb.109
%G fr
%F JTNB_1994__6_1_127_0
Théodore Tapsoba. Automates calculant la complexité de suites automatiques. Journal de Théorie des Nombres de Bordeaux, Volume 6 (1994) no. 1, pp. 127-134. doi : 10.5802/jtnb.109. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.109/

[1] S. Arson, Démonstration de l'existence de suites asymitriques infinies, Mat. Sb. 44 (1937), 769-777. | JFM: 63.0928.01 | Zbl: 0018.11503

[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. | JFM: 48.0786.06 | MR: 1501161

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

Cited by Sources: