The three-squares lemma for partial words with one hole

详细信息	查看全文 | 推荐本文 |

• 作者：F. Blanchet-Sadri^a ; ^{blanchet@uncg.edu} ; Robert Merca艧^b ; ^{robertmercas@gmail.com}
• 关键词：Combinatorics on words ; Partial words ; Squares ; Fine and Wilf&rsquo ; s periodicity lemma ; Three-squares lemma
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：13 April, 2012
• 卷：428
• 期：Complete
• 页码：1-9
• 文件大小：303 K

摘要

Partial words, or sequences over a finite alphabet that may have do-not-know symbols or holes, have been recently the subject of much investigation. Several interesting combinatorial properties have been studied such as the periodic behavior and the counting of distinct squares in partial words. In this paper, we extend the three-squares lemma on words to partial words with one hole. This result provides special information about the squares in a partial word with at most one hole, and puts restrictions on the positions at which periodic factors may occur, which is in contrast with the well known periodicity lemma of Fine and Wilf.