5 papers · 1 filter
Additive word complexity and Walnut
Pierre Popoli, Jeffrey Shallit, Manon Stipulanti
In combinatorics on words, a classical topic of study is the number of specific patterns appearing in infinite sequences. For instance, many works have been dedicated to studying t…
The Repetition Threshold for Rote Sequences
Nicolas Ollinger, Jeffrey Shallit
We consider Rote words, which are infinite binary words with factor complexity . We prove that the repetition threshold for this class is . Our technique is purely computa…
The reflection complexity of sequences over finite alphabets
Jean-Paul Allouche, John M. Campbell, Shuo Li +2
In combinatorics on words, the well-studied factor complexity function $ρ_{\infw{x}}$ of a sequence $\infw{x}$ over a finite alphabet counts, for every nonnegative integer , the…
Proof of Irvine's Conjecture via Mechanized Guessing
Jeffrey Shallit
We prove a recent conjecture of Sean A. Irvine about a nonlinear recurrence, using mechanized guessing and verification. The theorem-prover Walnut plays a large role in the proof.
Power-free Complementary Binary Morphisms
Jeffrey Shallit, Arseny M. Shur, Stefan Zorcic
We revisit the topic of power-free morphisms, focusing on the properties of the class of complementary morphisms. Such morphisms are defined over a -letter alphabet, and map the…