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.  
  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.  
  5. J.R. Büchi, Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math.6 (1960) 66-92.  
  6. V. Bruyère and G. Hansel, Bertrand numeration systems and recognizability. Theoret. Comput. Sci.181 (1997) 17-43.  
  7. A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory3 (1969) 186-192.  
  8. F. Durand, A generalization of Cobham's Theorem. Theory Comput. Systems31 (1998) 169-185.  
  9. S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974).  
  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.  
  12. Ch. Frougny, Representation of numbers and finite automata. Math. Systems Theory25 (1992) 37-60.  
  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.  
  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.  
  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.  
  16. Ch. Frougny and B. Solomyak, On the context-freeness of the θ-expansions of the integers. Internat. J. Algebra Comput.9 (1999) 347-350.  
  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.  
  19. D. Lind and B. Marcus, An Introduction to Symbolic Dynamics. Cambridge University Press (1995).  
  20. M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002).  
  21. W. Parry, On the β-expansions of real numbers. Acta Math. Acad. Sci. Hungar.11 (1960) 401-416.  
  22. Y. Puri and T. Ward, A dynamical property unique to the Lucas sequence. Fibonacci Quartely39 (2001) 398-402.  
  23. Y. Puri and T. Ward, Arithmetic and growth of periodic orbits. J. Integer Sequences4 (2001), Article 01.2.1.  
  24. A. Rényi, Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hungar.8 (1957) 477-493.  
  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.  

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.