Systèmes de numération et automates

Messaoudi, Ali

Comptes Rendus. Mathématique, Tome 334 (2002) no. 12, pp. 1043-1046.

Soit β un entier algébrique et hyperbolique de module strictement supérieur à 1. Considérons A un sous ensemble fini de $\mathbb{Q}\left[\beta \right]$ et $D_{\beta }=\{{({\mathrm{a}}_i,{\mathrm{b}}_i)}_{\mathrm{i}⩾0}\in {(\mathrm{A}\times \mathrm{A})}^{\mathbb{N}}\mid {\sum }_{\mathrm{i}=0}^{\infty }{a}_i{\beta }^{-\mathrm{i}}={\sum }_{\mathrm{i}=0}^{\infty }{b}_i{\beta }^{-\mathrm{i}}\}.$ Nous donnons une condition nécessaire et suffisante pour que D_β soit sofique. Comme conséquence, nous obtenons un résultat de Thurston (voir Corollaire 1). Nous traiterons aussi le cas où l'ensemble des chiffres A est donné par l'algorithme glouton et nous étudierons le lien avec le β-shift.

Let β be an hyperbolic algebraic integer of modulus greater than 1. Let A be a finite set of $\mathbb{Q}\left[\beta \right]$ and $D_{\beta }=\{{({\mathrm{a}}_i,{\mathrm{b}}_i)}_{\mathrm{i}⩾0}\in {(\mathrm{A}\times \mathrm{A})}^{\mathbb{N}}\mid {\sum }_{\mathrm{i}=0}^{\infty }{a}_i{\beta }^{-\mathrm{i}}={\sum }_{\mathrm{i}=0}^{\infty }{b}_i{\beta }^{-\mathrm{i}}\}.$ We give a necessary and sufficient condition for D_β to be sofic. As a consequence, we obtain a result due to Thurston (see Corollary 1). We also treat the case where the set of digits A is given by the greedy algorithm and study the connection with the β-shift.

[1] Blanchard, F. β-expansions and symbolic dynamics, Theoret. Comput. Sci., Volume 65 (1989), pp. 131-141

[2] Bertrand, A. Développement en base θ, répartition modulo un de la suite (xθⁿ)_n⩾0, langages codés et θ-shift, Bull. Soc. Math. France, Volume 114 (1986), pp. 271-323

[3] Eilenberg, S., Automata, Languages, and Machines, 1, Academic Press, New York, 1974

[4] A. Messaoudi, Autour du fractal de Rauzy, Thèse de l'Université de la Méditérranée, Aix-Marseille II, 1996

[5] A. Messaoudi, Double expansions and automata, soumis

[6] Thurston, W.P. Groups, Tilings, and Finite State Automata, Amer. Math. Soc. Colloq. Lectures, 1990