Back to search

McMaster University

STRUCTURAL FACTORIZATION OF SQUARES IN STRINGS

Abstract

dc:description.abstract

A balanced double square in a string x consists of two squares starting in the same position and of comparable lengths. We present a unique fac- torization of the longer square into primitive components refereed to as the canonical factorization and analyze its properties. In particular, we examine the inversion factors and the right and left inversion subfactors. All three substrings are collectively referred to as rare factors as they occur only twice in a signi cant portion of the larger square. The inversion factors were es- sential for determining the classi cation of mutual con gurations of double squares and thus providing the best-to-date upper bound of 11n=6 for the number of distinct squares in a string of length n by Deza, Franek, and Thierry. The right and left inversion subfactors have the advantage of being half the length of the inversion factors, thus providing a stronger dis- crimination property for a possible third square. This part of the thesis was published by Bai, Franek, and Smyth. The canonical factorization and the right and left inversion subfactors are used to formulate and prove a signi cantly stronger version of the New Periodicity Lemma by Fan, Puglisi, Smyth, and Turpin, 2006, that basically restricts what kind of a third square can exists in a balanced double square. This part of the thesis was published by Bai, Franek, and Smyth. The canonical factorization and the inversion factors are applied to for- mulate and prove a stronger version of the Three Squares Lemma by Crochemore and Rytter. This part of the thesis was published by Bai, Deza, and Franek.

Degree

thesis:*
Department dc:contributor.department
Computational Engineering and Science
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bai, Haoyue
Advisors dc:contributor.advisor
  • Deza, Antoine
  • Franek, Frantisek

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

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
citation

Bai, Haoyue. STRUCTURAL FACTORIZATION OF SQUARES IN STRINGS. 2017. http://hdl.handle.net/11375/21444