On multiplicatively dependent linear numeration systems, and periodic points

Frougny, Christiane

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 $\beta$ and $\gamma$ respectively, such that $\beta$ and $\gamma$ 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.

[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 $\varphi$, 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 $\theta$-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 $\beta$-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