Back to search

McMaster University

Completing the New Periodicity Lemma

Abstract

dc:description.abstract

<p>The “Three Squares Lemma” (Crochemore and Rytter 1995) famously explored the consequences of supposing that three squares occur at the same position in a string. Essentially, it showed that this phenomenon could not occur unless the longest of the three squares was at least the sum of the lengths of the other two. More recently, several papers (Fan et al. 2006; Franek, Fuller, et al. 2012; Kopylova and Smyth 2012; Simpson 2007) have greatly extended this result to a “New Periodicity Lemma” (NPL) by supposing that only two of the squares occur at the same position, with a third occurring in a neighbourhood to the right. The proof of the NPL involves fourteen subcases, twelve of which have been proven over the last seven years. In this thesis, we prove the final two remaining.</p>

Degree

thesis:*
Department dc:contributor.department
Computing and Software
Year dc:date.issued
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bland, Widmer
Advisor dc:contributor.advisor
  • Smyth, W.F.

Identifiers

dc:identifier.*
Dc Identifier Other
opendissertations/8917
9997
5495991

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Bland, Widmer. Completing the New Periodicity Lemma. 2014. http://hdl.handle.net/11375/14090