On multiplicatively dependent linear numeration systems, and periodic points

Christiane Frougny[1]

  • [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 (2002)

  • Volume: 36, Issue: 3, page 293-314
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Frougny, Christiane. "On multiplicatively dependent linear numeration systems, and periodic points." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 36.3 (2002): 293-314. <http://eudml.org/doc/245625>.

@article{Frougny2002,
abstract = {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.},
affiliation = {Université Paris 7 LIAFA, UMR 7089 CNRS 2 place Jussieu 75251 Paris Cedex 05 (France) and Université Paris 8},
author = {Frougny, Christiane},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {numeration system; Pisot number; finite automaton; periodic point; Pisot numerations; finite automata; multiplicatively dependent numeration bases; Parry numbers},
language = {eng},
number = {3},
pages = {293-314},
publisher = {EDP-Sciences},
title = {On multiplicatively dependent linear numeration systems, and periodic points},
url = {http://eudml.org/doc/245625},
volume = {36},
year = {2002},
}

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
PB - EDP-Sciences
VL - 36
IS - 3
SP - 293
EP - 314
AB - 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.
LA - eng
KW - numeration system; Pisot number; finite automaton; periodic point; Pisot numerations; finite automata; multiplicatively dependent numeration bases; Parry numbers
UR - http://eudml.org/doc/245625
ER -

References

top
  1. [1] M.-J. Bertin, A. Decomps–Guilloux, M. Grandet–Hugot, M. Pathiaux–Delefosse and J.-P. Schreiber, Pisot and Salem numbers. Birkhäuser (1992). Zbl0772.11041
  2. [2] A. Bertrand, Développements en base de Pisot et répartition modulo 1. C. R. Acad. Sci. Paris 285 (1977) 419-421. Zbl0362.10040MR447134
  3. [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. Zbl0695.10005
  4. [4] A. Bès, An extension of the Cobham–Semënov Theorem. J. Symb. Logic 65 (2000) 201-211. Zbl0958.03025
  5. [5] J.R. Büchi, Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. 6 (1960) 66-92. Zbl0103.24705MR125010
  6. [6] V. Bruyère and G. Hansel, Bertrand numeration systems and recognizability. Theoret. Comput. Sci. 181 (1997) 17-43. Zbl0957.11015MR1463527
  7. [7] A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3 (1969) 186-192. Zbl0179.02501MR250789
  8. [8] F. Durand, A generalization of Cobham’s Theorem. Theory Comput. Systems 31 (1998) 169-185. Zbl0895.68081
  9. [9] S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974). Zbl0317.94045MR530382
  10. [10] S. Fabre, Une généralisation du théorème de Cobham. Acta Arithm. 67 (1994) 197-208. Zbl0814.11015MR1292734
  11. [11] A.S. Fraenkel, Systems of numeration. Amer. Math. Monthly 92 (1985) 105-114. Zbl0568.10005MR777556
  12. [12] Ch. Frougny, Representation of numbers and finite automata. Math. Systems Theory 25 (1992) 37-60. Zbl0776.11005MR1139094
  13. [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. Zbl1152.11303MR1966116
  14. [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. Zbl1040.68061MR1723473
  15. [15] Ch. Frougny and B. Solomyak, On Representation of Integers in Linear Numeration Systems, in Ergodic theory of Z d -Actions, edited by M. Pollicott and K. Schmidt. Cambridge University Press, London Math. Soc. Lecture Note Ser. 228 (1996) 345-368. Zbl0856.11007MR1411227
  16. [16] Ch. Frougny and B. Solomyak, On the context-freeness of the θ -expansions of the integers. Internat. J. Algebra Comput. 9 (1999) 347-350. Zbl1041.11008MR1723472
  17. [17] G. Hansel, Systèmes de numération indépendants et syndéticité. Theoret. Comput. Sci. 204 (1998) 119-130. Zbl0952.68073MR1637516
  18. [18] M. Hollander, Greedy numeration systems and regularity. Theory Comput. Systems 31 (1998) 111-133. Zbl0895.68088MR1491655
  19. [19] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics. Cambridge University Press (1995). Zbl1106.37301MR1369092
  20. [20] M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002). Zbl1001.68093MR1905123
  21. [21] W. Parry, On the β -expansions of real numbers. Acta Math. Acad. Sci. Hungar. 11 (1960) 401-416. Zbl0099.28103MR142719
  22. [22] Y. Puri and T. Ward, A dynamical property unique to the Lucas sequence. Fibonacci Quartely 39 (2001) 398-402. Zbl1018.37009MR1866354
  23. [23] Y. Puri and T. Ward, Arithmetic and growth of periodic orbits. J. Integer Sequences 4 (2001), Article 01.2.1. Zbl1004.11013MR1873399
  24. [24] A. Rényi, Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hungar. 8 (1957) 477-493. Zbl0079.08901MR97374
  25. [25] A.L. Semënov, The Presburger nature of predicates that are regular in two number systems. Siberian Math. J. 18 (1977) 289-299. Zbl0411.03054MR450050
  26. [26] J. Shallit, Numeration systems, linear recurrences, and regular sets. Inform. Comput. 113 (1994) 331-347. Zbl0810.11006MR1285236

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.