Affordable Access

On multiplicatively dependent linear numeration systems, and periodic points

Authors
Publication Date
Disciplines
  • Mathematics

Abstract

ita0221.dvi Theoretical Informatics and Applications Theoret. Informatics Appl. 36 (2002) 293{314 DOI: 10.1051/ita:2002015 ON MULTIPLICATIVELY DEPENDENT LINEAR NUMERATION SYSTEMS, AND PERIODIC POINTS Christiane Frougny1, 2 Abstract. Two linear numeration systems, with characteristic poly- nomial 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. Mathematics Subject Classification. 11A63, 11A67, 11B39, 37B10, 68R15. 1. Introduction This work is about the conversion of integers represented in two different nu- meration systems, linked in a certain sense. Recall that the conversion between base 4 and base 2 is computable by a finite automaton, but that conversion be- tween base 3 and base 2 is not. More generally, two numbers p > 1 and q > 1 are said to be multiplicatively dependent if there exist positive integers k and ‘ such that pk = q‘. A set of natural numbers is said to be p-recognizable if the set of representations in base p of its elements is recognizable by a finite automa- ton. Bu˝chi has shown that the set fqn j n � 0g is p-recognizable only if p and q are multiplicatively dependent integers [5]. In contrast, the famous theorem of Cobham [7] states that the only sets of natural numbers that are both p- and q-recognizable, when p and q are two multiplicatively independent integers >1, Keywords and phrases: Numeration system, Pisot number, �nite automaton, periodic point. 1 LIAFA, UMR 7089 du CNRS, 2 place Jussieu, 75251 Paris Cedex 05, France; e-mail: [email protected] 2 Universit�e Paris 8, France c© EDP Sciences 2002 294 CH. FROUGNY are unions of arithmetic progressions, and thus are k-recognizable for a

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Linear numeration systems of order two

on Information and Computation Jan 01, 1988

Confluent linear numeration systems

on Theoretical Computer Science Jan 01, 1992

Multiple points of tilings associated with Pisot n...

on Theoretical Computer Science Jan 01, 2006

Numeration Systems, Linear Recurrences, and Regula...

on Information and Computation Jan 01, 1994
More articles like this..