Numeration systems, linear recurrences, and regular sets
type: Item
instance of: scholarly article
title: Numeration systems, linear recurrences, and regular sets
zbMATH Open document ID: 0810.11006
published in: Information and Computation
publication date: 1994-10-12T00:00:00Z
review text: The author studies numeration systems based on a strictly increasing sequence of integers \(u_ 0=1, u_ 1, u_ 2,\dots\), which are order- preserving (i.e. such that the lexicographical order on representation of integers is the same as the usual order on integers). He shows that, under some technical assumptions, if the set of all representations is regular, then the sequence \((u_ n)_{n\in \mathbb{N}}\) satisfies a linear recurrence. The author also notes the reverse is not true and gives an application to the Ostrowski numeration system. To prove these nice results the author needs intermediate interesting lemmas, one of which allows him to answer a question of D. Klarner: if \(f\) is a recognizable relation, then the set of lexicographically smallest strings, one chosen from each non-empty equivalence class of \(f\), is regular. Finally, as indicated by the author, a simple proof of his main theorem, in the particular case of the greedy algorithm, has been given by N. Lorand.
Mathematics Subject Classification ID: 11A67
Mathematics Subject Classification ID: 11B37
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 638559
zbMATH Keywords: regular languages
zbMATH Keywords: numeration systems
zbMATH Keywords: representation of integers
zbMATH Keywords: linear recurrence
author: Jeffrey Shallit
reviewed by: Jean-Paul Allouche
MaRDI profile type: Publication
OpenAlex ID: W2045761215
DOI: 10.1006/INCO.1994.1076
description: scientific article; zbMATH DE number 638559