Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/12777
Title: | Computational and Structural Approaches to Periodicities in Strings |
Authors: | Baker, Andrew R. |
Advisor: | Deza, Antoine Franek, Frantisek |
Department: | Computing and Software |
Keywords: | string;algorithm;run;word;periodicity;string algorithm;Theory and Algorithms;Theory and Algorithms |
Publication Date: | Apr-2013 |
Abstract: | <p>We investigate the function ρ<sub><em>d</em></sub>(<em>n</em>) = max { <em>r</em>(<em><strong>x</strong></em>) | <em><strong>x</strong></em> is a (<em>d</em>, <em>n</em>)-string } where <em>r</em>(<em><strong>x</strong></em>) is the number of runs in the string <em><strong>x</strong></em>, and a (<em>d</em>, <em>n</em>)-string is a string with length <em>n</em> and exactly <em>d</em> distinct symbols. Our investigation is motivated by the conjecture that ρ<sub><em>d</em></sub>(<em>n</em>) ≤ <em>n</em>-<em>d</em>. We present and discuss fundamental properties of the ρ<sub><em>d</em></sub>(<em>n</em>) function. The values of ρ<sub><em>d</em></sub>(<em>n</em>) are presented in the (<em>d</em>, <em>n</em>-<em>d</em>)-table with rows indexed by <em>d</em> and columns indexed by <em>n</em>-<em>d</em> which reveals the regularities of the function. We introduce the concepts of the r-cover and core vector of a string, yielding a novel computational framework for determining ρ<sub><em>d</em></sub>(<em>n</em>) values. The computation of the previously intractable instances is achieved via first computing a lower bound, and then using the structural properties to limit our exhaustive search only to strings that can possibly exceed this number of runs. Using this approach, we extended the known maximum number of runs in binary string from 60 to 74. In doing so, we find the first examples of run-maximal strings containing four consecutive identical symbols. Our framework is also applied for an arbitrary number of distinct symbols, <em>d</em>. For example, we are able to determine that the maximum number of runs in a string with 23 distinct symbols and length 46 is 23. Further, we discuss the structural properties of a shortest (<em>d</em>, <em>n</em>)-string <em><strong>x</strong></em> such that <em>r</em>(<em><strong>x</strong></em>) > <em>n</em>-<em>d</em>, should such a string exist.</p> |
URI: | http://hdl.handle.net/11375/12777 |
Identifier: | opendissertations/7635 8689 3540506 |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
fulltext.pdf | 574.96 kB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.