Computational and Structural Approaches to Periodicities in Strings

Abstract

<p>We investigate the function ρ_<em>d</em>(<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 ρ_<em>d</em>(<em>n</em>) ≤ <em>n</em>-<em>d</em>. We present and discuss fundamental properties of the ρ_<em>d</em>(<em>n</em>) function. The values of ρ_<em>d</em>(<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 ρ_<em>d</em>(<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>