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 158 times.
    This article's PDF has been downloaded 115 times.