Systèmes de numération et automates

Ali Messaoudi

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

Systèmes de numération et automates

Ali Messaoudi ¹

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

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

Résumé
Abstract

Soit β un entier algébrique et hyperbolique de module strictement supérieur à 1. Considérons A un sous ensemble fini de $ℚ [β]$ et $D_{β} = {{(a_{i}, b_{i})}_{i ⩾ 0} \in {(A \times A)}^{ℕ} ∣ \sum_{i = 0}^{\infty} a_{i} β^{- i} = \sum_{i = 0}^{\infty} b_{i} β^{- 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 $ℚ [β]$ and $D_{β} = {{(a_{i}, b_{i})}_{i ⩾ 0} \in {(A \times A)}^{ℕ} ∣ \sum_{i = 0}^{\infty} a_{i} β^{- i} = \sum_{i = 0}^{\infty} b_{i} β^{- 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.

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

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

Affiliations des auteurs :

Ali Messaoudi ¹

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

@article{CRMATH_2002__334_12_1043_0,
     author = {Ali Messaoudi},
     title = {Syst\`emes de num\'eration et automates},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1043--1046},
     publisher = {Elsevier},
     volume = {334},
     number = {12},
     year = {2002},
     doi = {10.1016/S1631-073X(02)02411-1},
     language = {fr},
}

TY  - JOUR
AU  - Ali Messaoudi
TI  - Systèmes de numération et automates
JO  - Comptes Rendus. Mathématique
PY  - 2002
SP  - 1043
EP  - 1046
VL  - 334
IS  - 12
PB  - Elsevier
DO  - 10.1016/S1631-073X(02)02411-1
LA  - fr
ID  - CRMATH_2002__334_12_1043_0
ER  -

%0 Journal Article
%A Ali Messaoudi
%T Systèmes de numération et automates
%J Comptes Rendus. Mathématique
%D 2002
%P 1043-1046
%V 334
%N 12
%I Elsevier
%R 10.1016/S1631-073X(02)02411-1
%G fr
%F CRMATH_2002__334_12_1043_0

Ali Messaoudi. Systèmes de numération et automates. Comptes Rendus. Mathématique, Volume 334 (2002) no. 12, pp. 1043-1046. doi : 10.1016/S1631-073X(02)02411-1. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/S1631-073X(02)02411-1/

Bibliographie
Cité par

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

[2] A. Bertrand 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] S. Eilenberg, 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] W.P. Thurston Groups, Tilings, and Finite State Automata, Amer. Math. Soc. Colloq. Lectures, 1990

Cité par Sources :

Commentaires - Politique