Catalog Home Page

Three overlapping squares: The general case characterized & applications

Bland, W. and Smyth, W.F. (2015) Three overlapping squares: The general case characterized & applications. Theoretical Computer Science, 596 . pp. 23-40.

[img]
PDF - Authors' Version
Embargoed until June 2017.

Link to Published Version: http://dx.doi.org/10.1016/j.tcs.2015.06.037
*Subscription may be required

Abstract

The “Three Squares Lemma” [9] 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 [10], [30], [21] and [13] 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 — in these cases also, similar restrictions apply. In this paper an alternative strategy is proposed: the consequences of having only two squares at neighbouring positions are carefully analyzed, and then the observation is made that the analysis applies in a straightforward way (though perhaps with complicated details) to the three neighbouring squares problem in its full generality. We then apply these new insights, first to proofs of the final two remaining unproved subcases (out of a total of 14) of the NPL [10], then to an instance of the more general problem.

Publication Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2015 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/27491
Item Control Page Item Control Page