Avoidable patterns in strings of symbols 论文

摘要

A word is just a finite string of letters. The word Wavoids the word U provided no substitution instance of Uis a subword of W. W is avoidable if on some finite alpha-bet there is an infinite collection of words each of whichavoids W. W is A th power-free if W avoids x , where x isa letter. We develope the theory of those endomorphismsof free semigroups which preserve A th power-freeness andemploy this theory to investigate &th power-free words.We go on to prove that every Mh power-free word on nletters is a subword of a maximal word of the same kind.Next we examine avoidable words in general and provethat all words of length at least 2