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.

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.