Portal de Periódicos da CAPES

Ostrowski-automatic sequences: Theory and applications

2021; Elsevier BV; Volume: 858; Linguagem: Inglês

10.1016/j.tcs.2021.01.018

1879-2294

Aseem Baranwal, Luke Schaeffer, Jeffrey Shallit,

Algorithms and Data Compression

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.