• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

STRUCTURAL FACTORIZATION OF SQUARES IN STRINGS

Bai, Haoyue 05 1900 (has links)
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)

Page generated in 0.4197 seconds