×

Automates finis et ensembles normaux. (Finite automata and normal sets). (French) Zbl 0576.10026

Soit \(u=(u_ n)_{n\in {\mathbb{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é à u soit exactement \({\mathbb{R}}\setminus {\mathbb{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.

MSC:

11J71 Distribution modulo one
11K06 General theory of distribution modulo \(1\)
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML

References:

[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. · 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. · 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. · 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. · 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. · 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. · 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. · Zbl 0317.94045
[13] D. FREEDMAN, Markov chains, 1971, Holden-Day. · 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. · 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. · 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. · 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. · 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. · Zbl 0553.10041
[22] R. C. READ, Graph theory and computing. 1972, Academic Press. · Zbl 0243.00006
[23] R. S. VARGA, Matrix iterative analysis. 1962, Prentice-Hall. · Zbl 0133.08602
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.