Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

The new periodicity lemma revisited

Bai, H., Franěk, F. and Smyth, W.F. (2016) The new periodicity lemma revisited. Discrete Applied Mathematics, 212 . pp. 30-36.

PDF - Authors' Version
Download (715kB) | Preview
Link to Published Version:
*Subscription may be required


In 2006, the New Periodicity Lemma (NPL) was published, showing that the occurrence of two squares starting at a position ii in a string necessarily precludes the occurrence of other squares of specified period in a specified neighbourhood of ii. 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.

Item Type: Journal Article
Murdoch Affiliation(s): School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2016 Elsevier B.V.
Item Control Page Item Control Page


Downloads per month over past year