Journal article
The new periodicity lemma revisited
Discrete Applied Mathematics, Vol.212, pp.30-36
2016
Abstract
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.
Details
- Title
- The new periodicity lemma revisited
- Authors/Creators
- H. Bai (Author/Creator) - McMaster UniversityF. Franěk (Author/Creator) - McMaster UniversityW.F. Smyth (Author/Creator) - The University of Western Australia
- Publication Details
- Discrete Applied Mathematics, Vol.212, pp.30-36
- Publisher
- Elsevier BV
- Identifiers
- 991005542743707891
- Copyright
- © 2016 Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
77 File views/ downloads
67 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Mathematics, Applied
- ESI research areas
- Engineering