Ostrowski numeration systems, addition and finite automata

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\subseteq {\mathbb{N}}^n$ is definable in $(\mathbb{N},+,V_a)$, where $V_a$ 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 non-zero 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 $(\mathbb{N},+,V_a)$ follows.

References in corpus (2)

• Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance
• Efficient Algorithms for Zeckendorf Arithmetic

Cited by in corpus (2)

• Decidability for Sturmian words
• Critical exponent of infinite balanced words via the Pell number system