Ostrowski-automatic sequences: theory and applications (Q2222098)

A so-called Ostrowski numeration system is defined to canonically represent integers based on the denominators of the convergents of the continued fraction of an irrational number. For instance, with the golden mean, we get back the classical Zeckendorf numeration system based on the Fibonacci sequence. Given an irrational, the authors construct an automaton that recognizes the addition relation in such a system. In order to recognize this relation, they use an automaton that reads three integers represented in their canonical representation, along with the sequence of continued fraction, in parallel. They discuss the implementation for quadratic irrationals which has been integrated in the automatic theorem prover Walnut. The software, based on the Büchi-Bruyère theorem and initially built for automatic sequences, is therefore extended to a wider setting. In the second part of the paper, they apply their constructions to several problems in combinatorics on words: repetitions and pattern avoidance, partial solution to a conjecture about critical exponents in balanced words and discussions about rich words and Lucas words.