Numeration systems, linear recurrences, and regular sets (Q1333266)

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.