Prague Stringology Conference 2013

Kazuhiko Kusano, Kazuyuki Narisawa and Ayumi Shinohara

On Morphisms Generating Run-Rich Strings

Abstract:
A run in a string is a periodic substring which is extendable neither to the left nor to the right with the same period. Strings containing many runs are of interest. In this paper, we focus on the series of strings {ψ(φi(a))}i ≥ 0 generated by two kinds of morphisms, φ : {a, b, c}{a, b, c}* and ψ : {a, b, c}{0, 1}*. We reveal a simple morphism φr plays a critical role to generate run-rich strings. Combined with a morphism ψ', the strings { ψ'(φ
i
r
(a))}i ≥ 0 achieves exactly the same lower bound as the current best lower bound for the maximum number ρ(n) of runs in a string of length n. Moreover, combined with another morphism ψ'', the strings { ψ''(φ
i
r
(a))}i ≥ 0 give a new lower bound for the maximum value σ(n) of the sum of exponents of runs in a string of length n.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation