<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> / Doctor of Philosophy (PhD)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/12777 |
| Date | 04 1900 |
| Creators | Baker, Andrew R. |
| Contributors | Deza, Antoine, Franek, Frantisek, Computing and Software |
| Source Sets | McMaster University |
| Detected Language | English |
| Type | thesis |
Page generated in 0.0147 seconds