Catalog Home Page

The total run length of a word

Glen, A. and Simpson, J. (2013) The total run length of a word. Theoretical Computer Science, 501 . pp. 41-48.

[img]
Preview
PDF - Authors' Version
Download (223kB)
Link to Published Version: http://dx.doi.org/10.1016/j.tcs.2013.06.004
*Subscription may be required

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 τ(n) is the maximum TRL over all words of length n. We show that n2/ 8<τ(n)<47n2/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 α, and some other results.

Publication Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2013 ElsevierB.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/17693
Item Control Page Item Control Page

Downloads

Downloads per month over past year