Back to search

McMaster University

Novel Structural Properties and An Improved Bound for the Number Distinct Squares in a Strings

Abstract

dc:description.abstract

Combinatorics on words explore words – often called strings in the com- puter science community, or monoids in mathematics – and their structural properties. One of the most studied question deals with repetitions which are a form of redundancy. The thesis focuses on estimating the maximum number of distinct squares in a string of length n. Our approach is to study the combinatorial properties of these overlapping structures, nested systems, and obtain insights into the intricate patterns that squares create. Determin- ing the maximum number of repetitions in a string is of interest in different fields such as biology and computer science. For example, the question arrises when one tries to bound the number of repetitions in a gene or in a computer file to be data compressed. Specific strings containing many repetitions are often of interest for additional combinatorial properties. After a brief review of earlier results and an introduction to the question of bounding the maxi- mum number of distinct squares, we present the combinatorial insights and techniques used to obtain the main result of the thesis: a strengthening of the universal upper bound obtained by Fraenkel and Simpson in 1998.

Degree

thesis:*
Department dc:contributor.department
Mathematics
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Thierry, Adrien
Advisor dc:contributor.advisor
  • Deza, Antoine

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

Thierry, Adrien. Novel Structural Properties and An Improved Bound for the Number Distinct Squares in a Strings. 2016. http://hdl.handle.net/11375/19299