Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/19299
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Deza, Antoine | - |
dc.contributor.author | Thierry, Adrien | - |
dc.date.accessioned | 2016-05-13T12:47:12Z | - |
dc.date.available | 2016-05-13T12:47:12Z | - |
dc.date.issued | 2016 | - |
dc.identifier.uri | http://hdl.handle.net/11375/19299 | - |
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. | en_US |
dc.language.iso | en | en_US |
dc.subject | Combinatorics on Words | en_US |
dc.subject | free monoid | en_US |
dc.subject | String Algorithms | en_US |
dc.title | Novel Structural Properties and An Improved Bound for the Number Distinct Squares in a Strings | en_US |
dc.type | Thesis | en_US |
dc.contributor.department | Mathematics | en_US |
dc.description.degreetype | Thesis | en_US |
dc.description.degree | Doctor of Philosophy (PhD) | en_US |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Thierry_Adrien-1179240-Phd_Thesis 2.4.pdf | Thesis | 820.71 kB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.