Automates finis et ensembles normaux

Christian Mauduit

Annales de l'institut Fourier (1986)

  • Volume: 36, Issue: 2, page 1-25
  • ISSN: 0373-0956

Abstract

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

How to cite

top

Mauduit, Christian. "Automates finis et ensembles normaux." Annales de l'institut Fourier 36.2 (1986): 1-25. <http://eudml.org/doc/74713>.

@article{Mauduit1986,
abstract = {Soit $u=(u_ n)_\{n\in \{\bf 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 $\{\bf R\}\setminus \{\bf 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.},
author = {Mauduit, Christian},
journal = {Annales de l'institut Fourier},
keywords = {strictly increasing sequence; finite automaton; normal set},
language = {fre},
number = {2},
pages = {1-25},
publisher = {Association des Annales de l'Institut Fourier},
title = {Automates finis et ensembles normaux},
url = {http://eudml.org/doc/74713},
volume = {36},
year = {1986},
}

TY - JOUR
AU - Mauduit, Christian
TI - Automates finis et ensembles normaux
JO - Annales de l'institut Fourier
PY - 1986
PB - Association des Annales de l'Institut Fourier
VL - 36
IS - 2
SP - 1
EP - 25
AB - Soit $u=(u_ n)_{n\in {\bf 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 ${\bf R}\setminus {\bf 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.
LA - fre
KW - strictly increasing sequence; finite automaton; normal set
UR - http://eudml.org/doc/74713
ER -

References

top
  1. [1] J. P. ALLOUCHE, Théorie des nombres et automates, Thèse d'État, 1983, Université de Bordeaux I. 
  2. [2] C. BERGE, Graphes et hypergraphes, 1973, Dunod. Zbl0332.05101MR50 #9639
  3. [3] J. BERSTEL, Sur les mots sans carré définis par un morphisme, Springer Lecture Notes in Computer Science, 71 (1979), 16-25. Zbl0425.20046MR81j:68104
  4. [4] J. BERSTEL, Mots infinis. Théorie des langages et complexité des algorithmes, Journées d'Avignon, oct. 1983. 
  5. [5] G. CHRISTOL, Ensembles presque-périodiques k-reconnaissables, Theorical Computer Science, 9 (1979), 141-145. Zbl0402.68044MR80e:68141
  6. [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. Zbl0472.10035MR82e:10092
  7. [7] G. CHRISTOL, T. KAMAE, M. MENDÈS-FRANCE et G. RAUZY, Spectral properties of automaton-generating sequences (communication privée). 
  8. [8] A. COBHAM, Uniform tag sequences, Math. Syst. Theory, vol. 6, n° 2 (1972), 164-192. Zbl0253.02029MR56 #15230
  9. [9] J. COQUET, Graphes connexes, représentation des entiers et équirépartition, Journ. of Number Theory, vol. 16, n° 3 (1983), 363-375. Zbl0512.10041MR84i:10053
  10. [10] J. COQUET et P. LIARDET, A metric study involving independent sequences (à paraître). Zbl0645.10044
  11. [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. Zbl0438.10040
  12. [12] S. EILENBERG, Automata, languages and machines, vol. A, 1974, Academic Press. Zbl0317.94045MR58 #26604a
  13. [13] D. FREEDMAN, Markov chains, 1971, Holden-Day. Zbl0212.49801MR45 #1263
  14. [14] F. HARARY, Graph theory, 1969, Addison-Wesley. Zbl0182.57702
  15. [15] L. KUIPERS et N. NIEDERREITER, Uniform distribution of sequences, 1974, John Wiley and Sons. Zbl0281.10001
  16. [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. Zbl0468.10019MR83i:10046
  17. [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. Zbl0565.10030MR85i:11066
  18. [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. Zbl0451.10018MR83b:10040
  19. [19] M. QUEFFELEC, Contribution à l'étude spectrale de suites arithmétiques, Thèse d'État, 1984, Université de Paris-Nord. 
  20. [20] G. RAUZY, Propriétés statistiques de suites arithmétiques, 1976, Presses Universitaires de France. Zbl0337.10036MR53 #13152
  21. [21] G. RAUZY, Des mots en arithmétique. Théorie des langages et complexité des algorithmes, Journées d'Avignon, oct. 1983. Zbl0553.10041
  22. [22] R. C. READ, Graph theory and computing. 1972, Academic Press. Zbl0243.00006MR48 #8280
  23. [23] R. S. VARGA, Matrix iterative analysis. 1962, Prentice-Hall. 

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.