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)
- Institution
- 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.
A generalization of Thue freeness for partial words
PDF (Portable Document Format)
335 KB
Created on 6/22/2011
Views: 2138
Additional Information
- Publication
- Theoretical Computer Science
- Language: English
- Date: 2009
- Keywords
- Combinatorics on words, Partial words, Thue–Morse word, Freeness, Square-freeness, Overlap-freeness