How many runs can a string contain?
In 2000 Kolpakov and Kucherov showed that the maximum number ρ(n) of runs in any string x[1..n] is O(n), but their proof was nonconstructive and provided no specific constant of proportionality. At the same time, they presented experimental data to prompt the conjecture: ρ(n)<n. Recently, Rytter...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier
2008
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/47398 |
| _version_ | 1848757821635559424 |
|---|---|
| author | Puglisi, S. Simpson, Jamie Smyth, William |
| author_facet | Puglisi, S. Simpson, Jamie Smyth, William |
| author_sort | Puglisi, S. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | In 2000 Kolpakov and Kucherov showed that the maximum number ρ(n) of runs in any string x[1..n] is O(n), but their proof was nonconstructive and provided no specific constant of proportionality. At the same time, they presented experimental data to prompt the conjecture: ρ(n)<n. Recently, Rytter [Wojciech Rytter, The number of runs in a string: Improved analysis of the linear upper bound, in: B. Durand, W. Thomas (Eds.), STACS 2006, in: Lecture Notes in Computer Science, vol. 3884, Springer-Verlag, Berlin, 2006, pp. 184–195] made a significant step toward proving this conjecture by showing that ρ(n)<5n. In this paper we improve Rytter’s approach and press the bound on ρ(n) further, proving ρ(n)≤3.48n. |
| first_indexed | 2025-11-14T09:34:11Z |
| format | Journal Article |
| id | curtin-20.500.11937-47398 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T09:34:11Z |
| publishDate | 2008 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-473982017-09-13T16:05:50Z How many runs can a string contain? Puglisi, S. Simpson, Jamie Smyth, William String periodicity run repetition In 2000 Kolpakov and Kucherov showed that the maximum number ρ(n) of runs in any string x[1..n] is O(n), but their proof was nonconstructive and provided no specific constant of proportionality. At the same time, they presented experimental data to prompt the conjecture: ρ(n)<n. Recently, Rytter [Wojciech Rytter, The number of runs in a string: Improved analysis of the linear upper bound, in: B. Durand, W. Thomas (Eds.), STACS 2006, in: Lecture Notes in Computer Science, vol. 3884, Springer-Verlag, Berlin, 2006, pp. 184–195] made a significant step toward proving this conjecture by showing that ρ(n)<5n. In this paper we improve Rytter’s approach and press the bound on ρ(n) further, proving ρ(n)≤3.48n. 2008 Journal Article http://hdl.handle.net/20.500.11937/47398 10.1016/j.tcs.2008.04.020 Elsevier unknown |
| spellingShingle | String periodicity run repetition Puglisi, S. Simpson, Jamie Smyth, William How many runs can a string contain? |
| title | How many runs can a string contain? |
| title_full | How many runs can a string contain? |
| title_fullStr | How many runs can a string contain? |
| title_full_unstemmed | How many runs can a string contain? |
| title_short | How many runs can a string contain? |
| title_sort | how many runs can a string contain? |
| topic | String periodicity run repetition |
| url | http://hdl.handle.net/20.500.11937/47398 |