On Representation of Integers in Linear Numeration Systems

C. FROUGNY, B. SOLOMYAK

IBP-Litp 1994/54: Rapport de Recherche Litp / Litp research reports
18 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: On Representation of Integers in Linear Numeration Systems

Résumé : On considère des systèmes de numération définis par une relation de récurrence linéaire à coefficients entiers. La normalisation est la fonction qui transforme une représentation quelconque d'un nombre entier positif selon le système de numération linéaire en sa représentation normale, obtenue par l'algorithme glouton. L'addition est un cas particulier de la normalisation. Nous montrons que, si le polynôme caractéristique de la récurrence linéaire est le polynôme minimal d'un nombre de Pisot, alors, pour tout alphabet fini d'entiers, la normalisation est une fonction calculable par 2-automate fini. Réciproquement, si le polynôme caractéristique est le polynôme minimal d'un nombre de Perron qui n'est pas un nombre de Pisot, alors il existe des alphabets sur lesquels la normalisation n'est pas calculable par 2-automate fini.

Abstract : Linear numeration systems defined by a linear recurrence relation with integer coefficients are considered. The normalization function maps any representation of a positive integer with respect to a linear numeration system onto the normal one, obtained by the greedy algorithm. Addition is a particular case of normalization. We show that if the characteristic polynomial of the linear recurrence is the minimal polynomial of a Pisot number, then normalization is a function computable by a finite 2-tape automaton on any finite alphabet of integers. Conversely, if the characteristic polynomial is the minimal polynomial of a Perron number which is not a Pisot number, then there exist alphabets on which normalization is not computable by a finite 2-tape automaton.

Publications internes Litp 1994 / Litp research reports 1994