Automates finis et ensembles normaux

Mauduit, Christian 

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

Résumé (VO)

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.

Abstract

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.

Détail

DOI : 10.5802/aif.1044