Abstract

We present an elementary three-pass algorithm for computing addition in Ostrowski numeration systems. When a is quadratic, addition in the Ostrowski numeration system based on a is recognizable by a finite automaton. We deduce that a subset of X⊆Nn is definable in, where Va is the function that maps a natural number x to the smallest denominator of a convergent of a that appears in the Ostrowski representation based on a of x with a nonzero coefficient if and only if the set of Ostrowski representations of elements of X is recognizable by a finite automaton. The decidability of the theory of follows.