On multiplicatively dependent linear numeration systems, and periodic points

Christiane Frougny

RAIRO - Theoretical Informatics and Applications (2010)

  • 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 36.3 (2010): 293-314. <http://eudml.org/doc/92703>.

@article{Frougny2010,
abstract = { 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. },
author = {Frougny, Christiane},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Numeration system; Pisot number; finite automaton; periodic point.; Pisot numerations; finite automata; multiplicatively dependent numeration bases; Parry numbers},
language = {eng},
month = {3},
number = {3},
pages = {293-314},
publisher = {EDP Sciences},
title = {On multiplicatively dependent linear numeration systems, and periodic points},
url = {http://eudml.org/doc/92703},
volume = {36},
year = {2010},
}

TY - JOUR
AU - Frougny, Christiane
TI - On multiplicatively dependent linear numeration systems, and periodic points
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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 β 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.
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/92703
ER -

References

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

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.