On multiplicatively dependent linear numeration systems, and periodic points
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 36, Issue: 3, page 293-314
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topFrougny, 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- M.-J. Bertin, A. Decomps-Guilloux, M. Grandet-Hugot, M. Pathiaux-Delefosse and J.-P. Schreiber, Pisot and Salem numbers. Birkhäuser (1992).
- A. Bertrand, Développements en base de Pisot et répartition modulo 1. C. R. Acad. Sci. Paris285 (1977) 419-421.
- 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.
- A. Bès, An extension of the Cobham-Semënov Theorem. J. Symb. Logic65 (2000) 201-211.
- J.R. Büchi, Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math.6 (1960) 66-92.
- V. Bruyère and G. Hansel, Bertrand numeration systems and recognizability. Theoret. Comput. Sci.181 (1997) 17-43.
- A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory3 (1969) 186-192.
- F. Durand, A generalization of Cobham's Theorem. Theory Comput. Systems31 (1998) 169-185.
- S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974).
- S. Fabre, Une généralisation du théorème de Cobham. Acta Arithm.67 (1994) 197-208.
- A.S. Fraenkel, Systems of numeration. Amer. Math. Monthly92 (1985) 105-114.
- Ch. Frougny, Representation of numbers and finite automata. Math. Systems Theory25 (1992) 37-60.
- 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.
- 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.
- 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.
- Ch. Frougny and B. Solomyak, On the context-freeness of the θ-expansions of the integers. Internat. J. Algebra Comput.9 (1999) 347-350.
- G. Hansel, Systèmes de numération indépendants et syndéticité. Theoret. Comput. Sci.204 (1998) 119-130.
- M. Hollander, Greedy numeration systems and regularity. Theory Comput. Systems31 (1998) 111-133.
- D. Lind and B. Marcus, An Introduction to Symbolic Dynamics. Cambridge University Press (1995).
- M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002).
- W. Parry, On the β-expansions of real numbers. Acta Math. Acad. Sci. Hungar.11 (1960) 401-416.
- Y. Puri and T. Ward, A dynamical property unique to the Lucas sequence. Fibonacci Quartely39 (2001) 398-402.
- Y. Puri and T. Ward, Arithmetic and growth of periodic orbits. J. Integer Sequences4 (2001), Article 01.2.1.
- A. Rényi, Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hungar.8 (1957) 477-493.
- A.L. Semënov, The Presburger nature of predicates that are regular in two number systems. Siberian Math. J.18 (1977) 289-299.
- J. Shallit, Numeration systems, linear recurrences, and regular sets. Inform. Comput.113 (1994) 331-347.
NotesEmbed ?
topYou 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.