Journal article
Three overlapping squares: The general case characterized & applications
Theoretical Computer Science, Vol.596, pp.23-40
2015
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.
Details
- Title
- Three overlapping squares: The general case characterized & applications
- Authors/Creators
- W. Bland (Author/Creator) - McMaster UniversityW.F. Smyth (Author/Creator) - Murdoch University
- Publication Details
- Theoretical Computer Science, Vol.596, pp.23-40
- Publisher
- Elsevier BV
- Identifiers
- 991005541699507891
- Copyright
- © 2015 Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
99 File views/ downloads
73 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
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science