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 .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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 215-232 |
| Number of pages | 18 |
| Journal | Notre Dame Journal of Formal Logic |
| Volume | 59 |
| Issue number | 2 |
| DOIs | |
| State | Published - 2018 |
Keywords
- Addition
- Continued fraction
- Decidability
- Expansion of Presburger arithmetic
- Finite automata
- Ostrowski numeration system
ASJC Scopus subject areas
- Logic