On the successor function in non-classical numeration systems

C. Frougny

IBP-Litp 1995/52: Rapport de Recherche Litp / Litp research reports
10 pages - Novembre/November 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: On the successor function in non-classical numeration systems

Résumé : Soit U une suite d'entiers strictement croissante, et soit L(U) l'ensemble des représentations gloutonnes des entiers positifs. La fonction successeur est la fonction qui envoie la représentation de N sur celle de N+1. On montre que la fonction successeur associée à U est calculable par un automate fini à deux bandes si et seulement si L(U) est reconnaissable par automate fini.

Abstract : Let U be a strictly increasing sequence of integers, and let L(U) be the set of greedy U-representations of all the nonnegative integers.The successor function maps the greedy U-representation of N onto the greedy U-representation of N+1.We show that the successor function associated to U is computable by a finite 2-tape automaton if and only if the set L(U) is recognizable by a finite automaton.

Publications internes Litp 1995 / Litp research reports 1995