James Currie ; Narad Rampersad - Low complexity binary words avoiding $(5/2)^+$-powers

dmtcs:15939 - Discrete Mathematics & Theoretical Computer Science, October 20, 2025, vol. 27:3 - https://doi.org/10.46298/dmtcs.15939
Low complexity binary words avoiding $(5/2)^+$-powersArticle

Authors: Narad Rampersad ; James Currie

Rote words are infinite words that contain $2n$ factors of length $n$ for every $n \geq 1$. Shallit and Shur, as well as Ollinger and Shallit, showed that there are Rote words that avoid $(5/2)^+$-powers and that this is best possible. In this note we give a structure theorem for the Rote words that avoid $(5/2)^+$-powers, confirming a conjecture of Ollinger and Shallit.

12 pages; main structure theorem restated to cover all cases for complementation/reversal of factors


Volume: vol. 27:3
Section: Combinatorics
Published on: October 20, 2025
Accepted on: October 15, 2025
Submitted on: June 25, 2025
Keywords: Combinatorics, Formal Languages and Automata Theory, 68R15

Consultation statistics

This page has been seen 312 times.
This article's PDF has been downloaded 277 times.