Automates finis et ensembles normaux
Mauduit, Christian
Annales de l'Institut Fourier, Tome 36 (1986), p. 1-25 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Soit u=(u n ) n∈N une suite strictement croissante d’entiers reconnaissable par un automate fini. Nous montrons qu’une condition nécessaire et suffisante pour que l’ensemble normal associé a u soit exactement R∖Q est que l’un au moins des sommets qui reconnaît la suite u soit précédé dans le graphe de l’automate par un sommet possédant au moins deux circuits fermés distincts. Cette condition peut se traduire quantitativement en disant que la suite u doit être plus “dense” que toute suite exponentielle.

Let u=(u n ) n∈N be a strictly increasing sequence of integers which is recognizable by a finite automaton. We show that the normal set with respect to u is equal to R∖Q if, and only if, in the oriented graph of the automaton, at least one of the vertices which recognize the sequence u is preceded by a vertex from which at least two closed circuits emerge. This condition can be reformulated in quantitative terms as follows: the sequence u must be “denser” than any exponential sequence.

@article{AIF_1986__36_2_1_0,
     author = {Mauduit, Christian},
     title = {Automates finis et ensembles normaux},
     journal = {Annales de l'Institut Fourier},
     volume = {36},
     year = {1986},
     pages = {1-25},
     doi = {10.5802/aif.1044},
     mrnumber = {87h:11071},
     zbl = {0576.10026},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/AIF_1986__36_2_1_0}
}

Mauduit, Christian. Automates finis et ensembles normaux. Annales de l'Institut Fourier, Tome 36 (1986) pp. 1-25. doi : 10.5802/aif.1044. http://gdmltest.u-ga.fr/item/AIF_1986__36_2_1_0/

[1] J. P. Allouche, Théorie des nombres et automates, Thèse d'État, 1983, Université de Bordeaux I.

[2] C. Berge, Graphes et hypergraphes, 1973, Dunod. | MR 50 #9639 | Zbl 0332.05101

[3] J. Berstel, Sur les mots sans carré définis par un morphisme, Springer Lecture Notes in Computer Science, 71 (1979), 16-25. | MR 81j:68104 | Zbl 0425.20046

[4] J. Berstel, Mots infinis. Théorie des langages et complexité des algorithmes, Journées d'Avignon, oct. 1983.

[5] G. Christol, Ensembles presque-périodiques k-reconnaissables, Theorical Computer Science, 9 (1979), 141-145. | MR 80e:68141 | Zbl 0402.68044

[6] G. Christol, T. Kamae, M. Mendès-France et G. Rauzy, Suites algébriques, automates et substitutions, Bull. Soc. Math. France, 108 (1980), 401-418. | Numdam | MR 82e:10092 | Zbl 0472.10035

[7] G. Christol, T. Kamae, M. Mendès-France et G. Rauzy, Spectral properties of automaton-generating sequences (communication privée).

[8] A. Cobham, Uniform tag sequences, Math. Syst. Theory, vol. 6, n° 2 (1972), 164-192. | MR 56 #15230 | Zbl 0253.02029

[9] J. Coquet, Graphes connexes, représentation des entiers et équirépartition, Journ. of Number Theory, vol. 16, n° 3 (1983), 363-375. | MR 84i:10053 | Zbl 0512.10041

[10] J. Coquet et P. Liardet, A metric study involving independent sequences (à paraître). | Zbl 0645.10044

[11] F. M. Dekking, Regularity and irregularity of sequences generated by automata. Séminaire de théorie des nombres, 1979-1980, Université de Bordeaux I. | Zbl 0438.10040

[12] S. Eilenberg, Automata, languages and machines, vol. A, 1974, Academic Press. | MR 58 #26604a | Zbl 0317.94045

[13] D. Freedman, Markov chains, 1971, Holden-Day. | MR 45 #1263 | Zbl 0212.49801

[14] F. Harary, Graph theory, 1969, Addison-Wesley. | Zbl 0182.57702

[15] L. Kuipers et N. Niederreiter, Uniform distribution of sequences, 1974, John Wiley and Sons. | Zbl 0281.10001

[16] J. H. Loxton et A. J. Van Der Poorten, Arithmetic properties of the solutions of a class of functional equations. J. Reine und Angew. Math., t. 330 (1982), 159-172. | MR 83i:10046 | Zbl 0468.10019

[17] C. Mauduit, Automates finis et équirépartition modulo un, C.R. A. S., Paris, t. 299, série I, n° 5 (1984), 121-123. | MR 85i:11066 | Zbl 0565.10030

[18] M. Mendès-France et A. J. Van Der Poorten, Arithmetic and analytic properties of paper folding sequences, Bull. Austral. Math. Soc., 24 (1981), 123-131. | MR 83b:10040 | Zbl 0451.10018

[19] M. Queffelec, Contribution à l'étude spectrale de suites arithmétiques, Thèse d'État, 1984, Université de Paris-Nord.

[20] G. Rauzy, Propriétés statistiques de suites arithmétiques, 1976, Presses Universitaires de France. | MR 53 #13152 | Zbl 0337.10036

[21] G. Rauzy, Des mots en arithmétique. Théorie des langages et complexité des algorithmes, Journées d'Avignon, oct. 1983.

[22] R. C. Read, Graph theory and computing. 1972, Academic Press. | MR 48 #8280 | Zbl 0243.00006

[23] R. S. Varga, Matrix iterative analysis. 1962, Prentice-Hall.