Systèmes de numération et automates

Messaoudi, Ali¹

¹ Departamento de Matemática, FEIS-UNESP, Av Brasil, 56 Caixa Postal 31, 15385-000, Ilha Solteira, SP, Brazil

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

Résumé (VO)

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.

Abstract

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.

Détail

Reçu le : 2002-04-02
Accepté le : 2002-04-04
Publié le : 2002-01-01

DOI : 10.1016/S1631-073X(02)02411-1