The total run length of a word
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 leng...
| Main Authors: | , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier
2013
|
| Online Access: | http://hdl.handle.net/20.500.11937/42452 |
| _version_ | 1848756423454883840 |
|---|---|
| author | Glen, A. Simpson, Jamie |
| author_facet | Glen, A. Simpson, Jamie |
| author_sort | Glen, A. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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+2nn2/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. |
| first_indexed | 2025-11-14T09:11:58Z |
| format | Journal Article |
| id | curtin-20.500.11937-42452 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T09:11:58Z |
| publishDate | 2013 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-424522019-02-19T04:27:57Z The total run length of a word Glen, A. Simpson, Jamie 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+2nn2/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. 2013 Journal Article http://hdl.handle.net/20.500.11937/42452 10.1016/j.tcs.2013.06.004 Elsevier fulltext |
| spellingShingle | Glen, A. Simpson, Jamie The total run length of a word |
| title | The total run length of a word |
| title_full | The total run length of a word |
| title_fullStr | The total run length of a word |
| title_full_unstemmed | The total run length of a word |
| title_short | The total run length of a word |
| title_sort | total run length of a word |
| url | http://hdl.handle.net/20.500.11937/42452 |