Automata calculating the complexity of automatic sequences. (Automates calculant la complexité de suites automatiques.) (French) Zbl 0815.11015

The complexity of a sequence on a finite alphabet is the function \(n \to \rho (n)\), where \(\rho (n)\) is the number of factors (blocks) of length \(n\) of the sequence. In the case where the sequence is a fixed point of a uniform injective substitution and where the sequence takes only two values, the author shows that if the sequence is minimal, then \(n \to \rho (n+1) - \rho (n)\) is generated by an automaton which is explicitly constructed. Note that, as indicated by the author, B. Mossé has obtained more general results (Preprint, LMD).
The paper ends with an example, the Thue-Morse sequence, for which the result of the author implies the previously known result of complexity [see A. de Luca and S. Varricchio, Theor. Comput. Sci. 63, 333-348 (1989; Zbl 0671.10050) and S. Brlek, Discrete Appl. Math. 24, 83-96 (1989; Zbl 0683.20045)].


11B85 Automata sequences
68Q45 Formal languages and automata
68R15 Combinatorics on words
Full Text: DOI Numdam EuDML EMIS


[1] Arson, S., Démonstration de l’existence de suites asymitriques infinies, Mat. Sb.44 (1937), 769-777. · JFM 63.0928.01
[2] Bleuzen-Guernalec, N., Suites points fixes de transductions uniformes, C. R. Acad. Sci. Paris, Série I 300 (1985), 85-88. · Zbl 0578.68069
[3] Brlek, S., Enumeration of factors in the Thue-Morse word, Discrete Applied Math.24 (1989), 83-96. · Zbl 0683.20045
[4] Christol, G., Kamae, T., Mendès France, M. et Rauzy, G., Suites algébriques, automates et substitutions, Bull. Soc. math. France108 (1980), 401-419. · Zbl 0472.10035
[5] Cobham, A., Uniform tag Sequences, Math. Systems Theory6 (1972), 164-192. · Zbl 0253.02029
[6] Gottschalk, W.H. and Hedlund, G.A., Topological dynamics, Am. Math. Soc. Colloq. Publ.36, Providence R. I. (1968). · Zbl 0067.15204
[7] Lothaire, Combinatorics on words, Addison Wesley MA (1982), chapter 12. · Zbl 0514.20045
[8] de Luca, A. and Varricchio, S., Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Theoret. Comput. Sci.63 (1989), 333-348. · Zbl 0671.10050
[9] Morse, M., Recurrent geodesic on a surface of negative curvate, Trans. Amer. Math. Soc.22 (1921), 84-100. · JFM 48.0786.06
[10] Queffélec, M., Contribution à l’étude spectrale de suites arithmétiques, Thèse d’État, Paris-Nord, (1984).
[11] Rauzy, G., 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] Tapsoba, T., Complexité de suites automatiques, Thèse de troisième cycle, Université Aix-Marseille II (1987). · Zbl 0815.11015
[13] Thue, A., Über unendliche Zeichenreihen, Norske Vid. Skr. I. Math. Kl., Christiana 7 (1906), 1-22. · JFM 37.0066.17
[14] Thue, A., Ü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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.