Logo image
Back
The total run length of a word
Journal article   Open access   Peer reviewed

The total run length of a word

A. Glen and J. Simpson
Theoretical Computer Science, Vol.501, pp.41-48
2013
DOI: https://doi.org/10.1016/j.tcs.2013.06.004
pdf
total_run_length_of_a_word.pdfDownloadView
Author’s Version Open Access
url
Link to Published Version *Subscription may be requiredView

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.

Details

Metrics

263 File views/ downloads
65 Record Views
4 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types
Domestic collaboration
Citation topics
4 Electrical Engineering, Electronics & Computer Science
4.182 Data Structures, Algorithms & Complexity
4.182.1103 Efficient Algorithms
Web Of Science research areas
Computer Science, Theory & Methods
ESI research areas
Computer Science
Logo image