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 .N;C; Va/, 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 .N;C; Va/ follows.
- Continued fraction
- Expansion of Presburger arithmetic
- Finite automata
- Ostrowski numeration system
ASJC Scopus subject areas