no. 3
On multiplicatively dependent linear numeration systems, and periodic points
Frougny, Christiane1
1 Université Paris 7 LIAFA, UMR 7089 CNRS 2 place Jussieu 75251 Paris Cedex 05 (France) and Université Paris 8
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 3, pp. 293-314.

Two linear numeration systems, with characteristic polynomial equal to the minimal polynomial of two Pisot numbers β and γ respectively, such that β and γ are multiplicatively dependent, are considered. It is shown that the conversion between one system and the other one is computable by a finite automaton. We also define a sequence of integers which is equal to the number of periodic points of a sofic dynamical system associated with some Parry number.

DOI : 10.1051/ita:2002015
Classification : 11A63, 11A67, 11B39, 37B10, 68R15
Mots clés : numeration system, Pisot number, finite automaton, periodic point
Frougny, Christiane 1

1 Université Paris 7 LIAFA, UMR 7089 CNRS 2 place Jussieu 75251 Paris Cedex 05 (France) and Université Paris 8 
@article{ITA_2002__36_3_293_0,
     author = {Frougny, Christiane},
     title = {On multiplicatively dependent linear numeration systems, and periodic points},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {293--314},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {3},
     year = {2002},
     doi = {10.1051/ita:2002015},
     mrnumber = {1958245},
     zbl = {1044.11004},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2002015/}
}
TY  - JOUR
AU  - Frougny, Christiane
TI  - On multiplicatively dependent linear numeration systems, and periodic points
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2002
SP  - 293
EP  - 314
VL  - 36
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2002015/
DO  - 10.1051/ita:2002015
LA  - en
ID  - ITA_2002__36_3_293_0
ER  - 
%0 Journal Article
%A Frougny, Christiane
%T On multiplicatively dependent linear numeration systems, and periodic points
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2002
%P 293-314
%V 36
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2002015/
%R 10.1051/ita:2002015
%G en
%F ITA_2002__36_3_293_0
Frougny, Christiane. On multiplicatively dependent linear numeration systems, and periodic points. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 3, pp. 293-314. doi : 10.1051/ita:2002015. http://archive.numdam.org/articles/10.1051/ita:2002015/

[1] M.-J. Bertin, A. Decomps-Guilloux, M. Grandet-Hugot, M. Pathiaux-Delefosse and J.-P. Schreiber, Pisot and Salem numbers. Birkhäuser (1992). | Zbl

[2] A. Bertrand, Développements en base de Pisot et répartition modulo 1. C. R. Acad. Sci. Paris 285 (1977) 419-421. | MR | Zbl

[3] A. Bertrand-Mathis, Comment écrire les nombres entiers dans une base qui n'est pas entière. Acta Math. Acad. Sci. Hungar. 54 (1989) 237-241. | Zbl

[4] A. Bès, An extension of the Cobham-Semënov Theorem. J. Symb. Logic 65 (2000) 201-211. | Zbl

[5] J.R. Büchi, Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. 6 (1960) 66-92. | MR | Zbl

[6] V. Bruyère and G. Hansel, Bertrand numeration systems and recognizability. Theoret. Comput. Sci. 181 (1997) 17-43. | MR | Zbl

[7] A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3 (1969) 186-192. | MR | Zbl

[8] F. Durand, A generalization of Cobham's Theorem. Theory Comput. Systems 31 (1998) 169-185. | Zbl

[9] S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974). | MR | Zbl

[10] S. Fabre, Une généralisation du théorème de Cobham. Acta Arithm. 67 (1994) 197-208. | MR | Zbl

[11] A.S. Fraenkel, Systems of numeration. Amer. Math. Monthly 92 (1985) 105-114. | MR | Zbl

[12] Ch. Frougny, Representation of numbers and finite automata. Math. Systems Theory 25 (1992) 37-60. | MR | Zbl

[13] Ch. Frougny, Conversion between two multiplicatively dependent linear numeration systems, in Proc. of LATIN 02. Springer-Verlag, Lectures Notes in Comput. Sci. 2286 (2002) 64-75. | MR

[14] Ch. Frougny and J. Sakarovitch, Automatic conversion from Fibonacci representation to representation in base ϕ, and a generalization. Internat. J. Algebra Comput. 9 (1999) 351-384. | MR | Zbl

[15] Ch. Frougny and B. Solomyak, On Representation of Integers in Linear Numeration Systems 228 (1996) 345-368. | MR | Zbl

[16] Ch. Frougny and B. Solomyak, On the context-freeness of the θ-expansions of the integers. Internat. J. Algebra Comput. 9 (1999) 347-350. | MR | Zbl

[17] G. Hansel, Systèmes de numération indépendants et syndéticité. Theoret. Comput. Sci. 204 (1998) 119-130. | MR | Zbl

[18] M. Hollander, Greedy numeration systems and regularity. Theory Comput. Systems 31 (1998) 111-133. | MR | Zbl

[19] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics. Cambridge University Press (1995). | MR | Zbl

[20] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002). | MR | Zbl

[21] W. Parry, On the β-expansions of real numbers. Acta Math. Acad. Sci. Hungar. 11 (1960) 401-416. | MR | Zbl

[22] Y. Puri and T. Ward, A dynamical property unique to the Lucas sequence. Fibonacci Quartely 39 (2001) 398-402. | MR | Zbl

[23] Y. Puri and T. Ward, Arithmetic and growth of periodic orbits. J. Integer Sequences 4 (2001), Article 01.2.1. | MR | Zbl

[24] A. Rényi, Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hungar. 8 (1957) 477-493. | MR | Zbl

[25] A.L. Semënov, The Presburger nature of predicates that are regular in two number systems. Siberian Math. J. 18 (1977) 289-299. | MR | Zbl

[26] J. Shallit, Numeration systems, linear recurrences, and regular sets. Inform. Comput. 113 (1994) 331-347. | MR | Zbl

Cité par Sources :