5 citations · 6 across the 7 of their papers we have counts for
5 papers · 1 filter
On the Number of Unbordered Factors
Daniel Goc, Hamoon Mousavi, Jeffrey Shallit
We illustrate a general technique for enumerating factors of k-automatic sequences by proving a conjecture on the number f(n) of unbordered factors of the Thue-Morse sequence. We s…
Least periods of k-automatic sequences
Daniel Goc, Jeffrey Shallit
Currie and Saari initiated the study of least periods of infinite words, and they showed that every integer n >= 1 is a least period of the Thue-Morse sequence. We generalize this…
Primitive Words and Lyndon Words in Automatic and Linearly Recurrent Sequences
Daniel Goc, Kalle Saari, Jeffrey Shallit
We investigate questions related to the presence of primitive words and Lyndon words in automatic and linearly recurrent sequences. We show that the Lyndon factorization of a k-aut…
Subword Complexity and k-Synchronization
Daniel Goc, Luke Schaeffer, Jeffrey Shallit
We show that the subword complexity function p_x(n), which counts the number of distinct factors of length n of a sequence x, is k-synchronized in the sense of Carpi if x is k-auto…
Automatic Theorem-Proving in Combinatorics on Words
Dane Henshall, Jeffrey Shallit
We describe a technique for mechanically proving certain kinds of theorems in combinatorics on words, using automata and a package for manipulating them. We illustrate our techniqu…