View Item 

On the maximal number of cubic runs in a string

Access Status
Fulltext not available
Authors
Crochemore, M.
Iliopoulos, Costas
Kubica, M.
Radoszewski, J.
Rytter, W.
Walen, T.
Date
2010
Collection
Type
Conference Paper
Metadata
Show full item record
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.

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.
Source Title
Lecture notes in computer science, volume 6031: language and automata theory and applications - LATA 2010
URI
DOI
Additional URLs
School
Digital Ecosystems and Business Intelligence Institute (DEBII)