The Prague Stringology Conference 2009

Reducing Repetitions

Abstract:

For a given word w, all the square-free words that can be reached by successive application of rewriting rules uu → u constitute w's duplication root. One word can have several such roots. We provide upper and lower bounds on the maximal number of duplication roots of words of length n that show that this number is at least exponential in n.