Date of Award
2015
Document Type
Open Access Dissertation
Department
Mathematics
Sub-Department
College of Arts and Sciences
First Advisor
George F. McNulty
Abstract
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, Dalalyan showed that each doubled word is 4-avoidable and that each doubled word on 6 or more letters is 3-avoidable. In 2013, Blanchet-Sadri and Woodhouse, building on the work of Bell and Goh that is similar to Dalalyan, strengthened the result by showing that all doubled words of length at least 12 are 3-avoidable. Cassaigne in his dissertation classified all the words on the 2-letter alphabet and most of the words on the 3-letter alphabet, and as a result, showed that each doubled word in which at most most 3 distinct letters appear is 3-avoidable. These results leave 7441 doubled words in which exactly 4 or 5 distinct letters appear to check for 3-avoidability. In this dissertation, we show that each doubled word in which at least one letter occurs 3 or more times is 3-avoidable. This leaves only the doubled words to check for 3-avoidability in which exactly 4 or 5 letters appear in the word and each letter appears exactly twice. In fact, we give a list of just 99 doubled words so that if each word on the list can be shown to be 3-avoidable, then we would know that each doubled word is 3-avoidable.
Rights
© 2015, Michael Lane
Recommended Citation
Lane, M.(2015). Avoiding Doubled Words in Strings of Symbols. (Doctoral dissertation). Retrieved from https://scholarcommons.sc.edu/etd/3689