On the maximal number of cubic runs in a string
| dc.contributor.author | Crochemore, M. | |
| dc.contributor.author | Iliopoulos, Costas | |
| dc.contributor.author | Kubica, M. | |
| dc.contributor.author | Radoszewski, J. | |
| dc.contributor.author | Rytter, W. | |
| dc.contributor.author | Walen, T. | |
| dc.contributor.editor | Adrian-Horia Dediu | |
| dc.contributor.editor | Henning Fernau | |
| dc.contributor.editor | Carlos Martin-Vide | |
| dc.date.accessioned | 2017-01-30T15:23:14Z | |
| dc.date.available | 2017-01-30T15:23:14Z | |
| dc.date.created | 2015-03-03T20:13:40Z | |
| dc.date.issued | 2010 | |
| dc.identifier.citation | Crochemore, M. and Iliopoulos, C. and Kubica, M. and Radoszewski, J. and Rytter, W. and Walen, T. 2010. On the maximal number of cubic runs in a string, in Adrian-Horia Dediu, Henning Fernau and Carlos Martin-Vide (ed), 4th International Conference on Language and Automata Theory and Applications, LATA 2010, May 24 2010, pp. 227-238. Trier: Springer. | |
| dc.identifier.uri | http://hdl.handle.net/20.500.11937/45763 | |
| dc.identifier.doi | 10.1007/978-3-642-13089-2_19 | |
| dc.description.abstract |
A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition v with a period p such that 2p =|v|.The maximal number of runs in a string of length n has been thoroughly studied, and is known to be between 0.944 n and 1.029 n.In this paper we investigate cubic runs, in which the shortest period p satis?es 3p =|v|. We show the upper bound of 0.5 n on the maximal number of such runs in a string of length n, and construct an in?nite sequence of words over binary alphabet for which the lower bound is 0.406 n. | |
| dc.publisher | Springer | |
| dc.relation.uri | http://www.springerlink.com/content/73w55281j86r8w18 | |
| dc.title | On the maximal number of cubic runs in a string | |
| dc.type | Conference Paper | |
| dcterms.source.startPage | 227 | |
| dcterms.source.endPage | 238 | |
| dcterms.source.title | Lecture notes in computer science, volume 6031: language and automata theory and applications - LATA 2010 | |
| dcterms.source.series | Lecture notes in computer science, volume 6031: language and automata theory and applications - LATA 2010 | |
| dcterms.source.isbn | 9783642130885 | |
| dcterms.source.conference | 4th International Conference on Language and Automata Theory and Applications, LATA 2010 | |
| dcterms.source.conference-start-date | May 24 2010 | |
| dcterms.source.conferencelocation | Trier | |
| dcterms.source.place | Heidelberg | |
| curtin.department | Digital Ecosystems and Business Intelligence Institute (DEBII) | |
| curtin.accessStatus | Fulltext not available |