Automates finis et ensembles normaux
Annales de l'Institut Fourier, Tome 36 (1986) no. 2, pp. 1-25.

Soit u=(un)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=(un)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},
     pages = {1--25},
     publisher = {Institut Fourier},
     address = {Grenoble},
     volume = {36},
     number = {2},
     year = {1986},
     doi = {10.5802/aif.1044},
     mrnumber = {87h:11071},
     zbl = {0576.10026},
     language = {fr},
     url = {https://www.numdam.org/articles/10.5802/aif.1044/}
}
TY  - JOUR
AU  - Mauduit, Christian
TI  - Automates finis et ensembles normaux
JO  - Annales de l'Institut Fourier
PY  - 1986
SP  - 1
EP  - 25
VL  - 36
IS  - 2
PB  - Institut Fourier
PP  - Grenoble
UR  - https://www.numdam.org/articles/10.5802/aif.1044/
DO  - 10.5802/aif.1044
LA  - fr
ID  - AIF_1986__36_2_1_0
ER  - 
%0 Journal Article
%A Mauduit, Christian
%T Automates finis et ensembles normaux
%J Annales de l'Institut Fourier
%D 1986
%P 1-25
%V 36
%N 2
%I Institut Fourier
%C Grenoble
%U https://www.numdam.org/articles/10.5802/aif.1044/
%R 10.5802/aif.1044
%G fr
%F AIF_1986__36_2_1_0
Mauduit, Christian. Automates finis et ensembles normaux. Annales de l'Institut Fourier, Tome 36 (1986) no. 2, pp. 1-25. doi : 10.5802/aif.1044. https://www.numdam.org/articles/10.5802/aif.1044/

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

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

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

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

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

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

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

[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

[12] S. Eilenberg, Automata, languages and machines, vol. A, 1974, Academic Press. | MR | Zbl

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

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

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

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

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

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

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

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

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

Cité par Sources :