On the amortized complexity of the odometer

Michel Rigo

Université de Liège, Belgium

Coauthor(s): Valérie Berthé, Christiane Frougny, and Jacques Sakarovitch

As usual, the odometer function $s$ maps the representation of an integer $n$ onto the representation of its successor $n+1$ in a given numeration system. In a general setting, i.e., for abstract numeration systems, the odometer maps a word from a rational language $L$ onto the next word $s(w)$ in $L$ assuming that $L$ has been genealogically ordered. The number $k(w)$ of operations for computing $s(w)$ is defined as $\vert s(w)\vert-\vert p(w,s(w))\vert$ where $p(x,y)$ denotes the longuest common prefix of $x$ and $y$. We estimate the sum of the $k(w)$'s for all the words of length $n$ in a given rational language $L$ and we compare this quantity with the number of words of length $n$ in $L$. If we assume that the automaton accepting $L$ has a primitive adjacency matrix having $\beta$ as Perron eigenvalue, this ratio tends to $\beta/(\beta-1)$ if $n$ tends to infinity. In particular, this results holds for beta-numeration systems built on a Parry number.