The New Periodicity Lemma revisited

详细信息    查看全文

• 作者：Haoyue Bai^a ; ^{baih3@mcmaster.ca" class="auth_mail" title="E-mail the corresponding author} ; Frantisek Franek^a ; ^{franek@mcmaster.ca" class="auth_mail" title="E-mail the corresponding author} ; William F. Smyth^a ; ^b ; ^c ; ^{bill@arg.cas.mcmaster.ca" class="auth_mail" title="E-mail the corresponding author}
• 关键词：String ; Square ; Canonical factorization ; Double square ; New Periodicity Lemma
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：30 October 2016
• 年：2016
• 卷：212
• 期：Complete
• 页码：30-36
• 全文大小：475 K

文摘

In 2006, the New Periodicity Lemma   (NPL) was published, showing that the occurrence of two squares starting at a position i$i$ in a string necessarily precludes the occurrence of other squares of specified period in a specified neighbourhood of i$i$. The proof of this lemma was complex, breaking down into 14 subcases, and requiring that the shorter of the two squares be regular. In this paper we significantly relax the conditions required by the NPL and removing the need for regularity altogether, and we establish a more precise result using a simpler proof based on lemmas that expose new combinatorial structures in a string, in particular a canonical factorization for any two squares that start at the same position.