On the maximal number of cubic runs in a string

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

School

Digital Ecosystems and Business Intelligence Institute (DEBII)

URI

http://hdl.handle.net/20.500.11937/45763

Collection

Curtin Research Publications

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.