James D. Currie ; Lucas Mol ; Narad Rampersad - The repetition threshold for binary rich words

dmtcs:5791 - Discrete Mathematics & Theoretical Computer Science, February 24, 2020, vol. 22 no. 1 - https://doi.org/10.23638/DMTCS-22-1-6
The repetition threshold for binary rich wordsArticle

Authors: James D. Currie ; Lucas Mol ; Narad Rampersad

    A word of length n is rich if it contains n nonempty palindromic factors. An infinite word is rich if all of its finite factors are rich. Baranwal and Shallit produced an infinite binary rich word with critical exponent 2+2/2 (2.707) and conjectured that this was the least possible critical exponent for infinite binary rich words (i.e., that the repetition threshold for binary rich words is 2+2/2). In this article, we give a structure theorem for infinite binary rich words that avoid 14/5-powers (i.e., repetitions with exponent at least 2.8). As a consequence, we deduce that the repetition threshold for binary rich words is 2+2/2, as conjectured by Baranwal and Shallit. This resolves an open problem of Vesti for the binary alphabet; the problem remains open for larger alphabets.


    Volume: vol. 22 no. 1
    Section: Analysis of Algorithms
    Published on: February 24, 2020
    Accepted on: January 13, 2020
    Submitted on: September 27, 2019
    Keywords: Mathematics - Combinatorics,Computer Science - Formal Languages and Automata Theory,68R15

    Classifications

    Mathematics Subject Classification 20201

    Publications

    Has review
    • 1 zbMATH Open

    1 Document citing this article

    Consultation statistics

    This page has been seen 1735 times.
    This article's PDF has been downloaded 382 times.