The total run length of a word

Abstract

A run in a word is a periodic factor whose length is at least twice its period and which cannot be extended to the left or right (by a letter) to a factor with greater period. In recent years a great deal of work has been done on estimating the maximum number of runs that can occur in a word of length $n$. A number of associated problems have also been investigated. In this paper we consider a new variation on the theme. We say that the total run length (TRL) of a word is the sum of the lengths of the runs in the word and that $\tau (n)$ is the maximum TRL over all words of length $n$. We show that $n^2/8<\tau (n)<47n^2/72+2n$ for all $n$. We also give a formula for the average total run length of words of length $n$ over an alphabet of size $\alpha$, and some other results.

11 pages; minor corrections; accepted for publication in Theoretical Computer Science