A generalization of Thue freeness for partial words

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Francine Blanchet-Sadri, Professor (Creator)
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

Abstract: This paper approaches the combinatorial problem of Thue freeness for partial words. Partial words are sequences over a finite alphabet that may contain a number of ?holes?. First, we give an infinite word over a three-letter alphabet which avoids squares of length greater than two even after we replace an infinite number of positions with holes. Then, we give an infinite word over an eight-letter alphabet that avoids longer squares even after an arbitrary selection of its positions are replaced with holes, and show that the alphabet size is optimal. We find similar results for overlap-free partial words.

Additional Information

Theoretical Computer Science
Language: English
Date: 2009
Combinatorics on words, Partial words, Thue–Morse word, Freeness, Square-freeness, Overlap-freeness

Email this document to