The Prague Stringology Conference 2009

Peter Leupold

Reducing Repetitions

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.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation