2012/12/01 by Hamoon Mousavi, Jeffrey Shallit, Mousavi, Hamoon +1
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #cs.FL #math.CO
paper · pdf · doi:10.48550/arxiv.1212.0052
12 pages; added references; DLT 2013 conference
arxiv created 2013/03/17 · arxiv updated 2013/03/19
We consider the following novel variation on a classical avoidance problem from combinatorics on words: instead of avoiding repetitions in all factors of a word, we avoid repetitions in all factors where each individual factor is considered as a "circular word", i.e., the end of the word wraps around to the beginning. We determine the best possible avoidance exponent for alphabet size 2 and 3, and provide a lower bound for larger alphabets.