Physical Sciences and Mathematics Commons^™

Avoiding Doubled Words In Strings Of Symbols, Michael Lane

Theses and Dissertations

A word on the n-letter alphabet is a finite length string of symbols formed from a set of n letters. A word is doubled if every letter that appears in the word appears at least twice. A word w avoids a word u if there is no non-erasing homomorphism h (a map that respects concatenation) such that h (u) is a subword of w. Finally, a word w is n-avoidable if there is an infinite list of words on the n-letter alphabet that avoid w. In 1906, Thue showed that the simplest doubled word, namely xx, is 3-avoidable. In 1984, …