Automates finis et ensembles normaux

Mauduit, Christian

Annales de l'Institut Fourier, Tome 36 (1986) no. 2, pp. 1-25.

Soit $u=(u_n{)}_{n\in \mathbf{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 $\mathbf{R}\setminus \mathbf{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\in \mathbf{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 $\mathbf{R}\setminus \mathbf{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.

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