numeration systems; positional numeration system; regular language
Abstract :
[en] In this talk, we study positional numeration systems and whether they generate a regular language. In a positional numeration system, a sequence $(U_n)_{n\in\mathbb{N}}$ is given, then every number is decomposed as a sum of terms in $U$ and a word that represents this number is deduced from this decomposition. The language $L_U$ of such a system, i.e., the set of all representations, can be regular or not, depending on the sequence $U$.
In 1998, Hollander provided some necessary and some sufficient conditions on $U$ for the language to be regular. He did so by leveraging a connection between numeration systems with a dominant root (i.e., such that the limit $\lim_{n\to\infty}\frac{U_{n+1}}{U_n}$ exists) and Rényi numeration systems. However, not every positional numeration system that has a regular language has a dominant root.
In our talk, we relax this hypothesis and provide a criterion for the regularity of $L_U$ even when $U$ has no dominant root. Our main tool is the introduction of alternate bases, a generalization of Rényi numeration systems that replaces them when the dominant root condition is dropped. This allows us to reuse some of Hollander's lemmas in our more general setting, and to finely study the algorithm that represents numbers.
Joint work with Emilie Charlier.
