Skip to main content

The Successor Function for Minimal Words in Rational Base Numeration Systems

Victor Marsault ( IRIF, Paris 7 )

Rational base numeration systems were introduced by Akiyama, Frougny and
Sakarovitch in 2008 and allowed to make some progress in a number theoretic
problem, by means of automata theory and combinatorics of words.  At the
same time, they raised the problem of understanding the structure of the
sets of the representations of the integers in these systems from the point
of view of formal language theory.

We present here a contribution to the study of this language.  Since it is
prefix-closed, it is naturally represented as an highly non-regular
(infinite) tree whose nodes are the integers and whose subtrees are
pairwise distinct.  With every node of that tree is then associated a
minimal infinite word and we study the function that computes for all n the
minimal word associated with (n+1) from the one associated with n.  The
main result is that this function is realised by an infinite, sequential
and letter-to-letter transducer which has essentially the same underlying
graph as the tree itself.

These infinite words are then interpreted as representations of real
numbers; the difference between the numbers represented by these two
consecutive minimal words is the called the span of a node of the tree.
The preceding construction allows to characterise the topological closure
of the set of spans.

Share this: