Automates calculant la complexité de suites automatiques

Théodore Tapsoba

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

  • Volume: 6, Issue: 1, page 127-134
  • ISSN: 1246-7405

Abstract

top
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 n → P ( u , n + 1 ) - P ( u , n ) is obtained by an automaton which is built explicitly.

How to cite

top

Tapsoba, Théodore. "Automates calculant la complexité de suites automatiques." Journal de théorie des nombres de Bordeaux 6.1 (1994): 127-134. <http://eudml.org/doc/247539>.

@article{Tapsoba1994,
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)$.},
author = {Tapsoba, Théodore},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {automatic sequences; complexity; Thue-Morse sequence},
language = {fre},
number = {1},
pages = {127-134},
publisher = {Université Bordeaux I},
title = {Automates calculant la complexité de suites automatiques},
url = {http://eudml.org/doc/247539},
volume = {6},
year = {1994},
}

TY - JOUR
AU - Tapsoba, Théodore
TI - Automates calculant la complexité de suites automatiques
JO - Journal de théorie des nombres de Bordeaux
PY - 1994
PB - Université Bordeaux I
VL - 6
IS - 1
SP - 127
EP - 134
AB - 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)$.
LA - fre
KW - automatic sequences; complexity; Thue-Morse sequence
UR - http://eudml.org/doc/247539
ER -

References

top
  1. [1] S. Arson, Démonstration de l'existence de suites asymitriques infinies, Mat. Sb.44 (1937), 769-777. Zbl0018.11503JFM63.0928.01
  2. [2] N. Bleuzen-Guernalec, Suites points fixes de transductions uniformes, C. R. Acad. Sci. Paris, Série I300 (1985), 85-88. Zbl0578.68069MR777740
  3. [3] S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math.24 (1989), 83-96. Zbl0683.20045MR1011264
  4. [4] 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
  5. [5] A. Cobham, Uniform tag Sequences, Math. Systems Theory6 (1972), 164-192. Zbl0253.02029MR457011
  6. [6] W.H. Gottschalk and G.A. Hedlund, Topological dynamics, Am. Math. Soc. Colloq. Publ.36, Providence R. I. (1968). Zbl0067.15204MR74810
  7. [7] Lothaire, Combinatorics on words, Addison Wesley MA (1982), chapter 12. Zbl0514.20045
  8. [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. Zbl0671.10050MR993769
  9. [9] M. Morse, Recurrent geodesic on a surface of negative curvate, Trans. Amer. Math. Soc.22 (1921), 84-100. MR1501161JFM48.0786.06
  10. [10] M. Queffélec, Contribution à l'étude spectrale de suites arithmétiques, Thèse d'État, Paris-Nord, (1984). 
  11. [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. Zbl0726.11019
  12. [12] T. Tapsoba, Complexité de suites automatiques, Thèse de troisième cycle, Université Aix-Marseille II (1987). 
  13. [13] A. Thue, Über unendliche Zeichenreihen, Norske Vid. Skr. I. Math. Kl., Christiana 7 (1906), 1-22. JFM37.0066.17
  14. [14] A. Thue, Über die gegenseitige Lage gleicher Teile genvisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Math. Nat. Kl., Christiana 1 (1912), 1-67. JFM44.0462.01

NotesEmbed ?

top

You must be logged in to post comments.