Ostrowski numeration systems, addition, and finite automata

Philipp Hieronymi, Alonza Terry

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)215-232
Number of pages18
JournalNotre Dame Journal of Formal Logic
Issue number2
StatePublished - 2018


  • Addition
  • Continued fraction
  • Decidability
  • Expansion of Presburger arithmetic
  • Finite automata
  • Ostrowski numeration system

ASJC Scopus subject areas

  • Logic


Dive into the research topics of 'Ostrowski numeration systems, addition, and finite automata'. Together they form a unique fingerprint.

Cite this