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. / Thesis / Doctor of Philosophy (PhD)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/21444 |
| Date | 05 1900 |
| Creators | Bai, Haoyue |
| Contributors | Deza, Antoine, Franek, Frantisek, Computational Engineering and Science |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0017 seconds