Ostrowski-automatic sequences: Theory and applications

We extend the notion of k-automatic sequences to Ostrowski-automatic sequences, and develop a procedure to computationally decide certain combinatorial and enumeration questions about such sequences that can be expressed as predicates in first-order logic. Our primary contribution is the design and implementation of an adder recognizing addition in a generalized Ostrowski numeration system. We also provide applications of our work to several topics in combinatorics on words, including repetitions and pattern avoidance. We partially resolve a previous conjecture about balanced words by Rampersad et al. , and make the first progress on an open problem on rich words by Vesti. We also prove some known results about Lucas words using only machine computation.

Authors

• Aseem Baranwal
• Luke Schaeffer
• Jeffrey Shallit

Keywords

• Decision procedure
• Automatic sequence
• Ostrowski numeration
• Repetition
• Balanced word
• Palindrome-rich word
• Lucas word