7 papers
The Simplest Binary Word with Only Three Squares
Daniel Gabric, Jeffrey Shallit
We re-examine previous constructions of infinite binary words containing few distinct squares with the goal of finding the "simplest", in a certain sense. We exhibit several new co…
An inequality for the number of periods in a word
Daniel Gabric, Narad Rampersad, Jeffrey Shallit
We prove an inequality for the number of periods in a word x in terms of the length of x and its initial critical exponent. Next, we characterize all periods of the length-n prefix…
Avoidance of split overlaps
Daniel Gabric, Jeffrey Shallit
We generalize Axel Thue's familiar definition of overlaps in words, and show that there are no infinite words containing split occurrences of these generalized overlaps. Along the…
Borders, Palindrome Prefixes, and Square Prefixes
Daniel Gabric, Jeffrey Shallit
We show that the number of length-n words over a k-letter alphabet having no even palindromic prefix is the same as the number of length-n unbordered words, by constructing an expl…
Circularly squarefree words and unbordered conjugates: a new approach
Trevor Clokie, Daniel Gabric, Jeffrey Shallit
Using a new approach based on automatic sequences, logic, and a decision procedure, we reprove some old theorems about circularly squarefree words and unbordered conjugates in a ne…
Maximal State Complexity and Generalized de Bruijn Words
Daniel Gabric, Štěpán Holub, Jeffrey Shallit
We compute the exact maximum state complexity for the language consisting of words of length , and characterize languages achieving the maximum. We also consider a special c…