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
Type
Conference Paper

Metadata
Show full item record
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
Source Conference
4th International Conference on Language and Automata Theory and Applications, LATA 2010
DOI
Additional URLs
ISBN
School
Digital Ecosystems and Business Intelligence Institute (DEBII)
URI
Collection
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.