#
Problem 84: Cubic Runs

Cubic runs constitute a particular case of runs for which bounds are easier
to evaluate.
As runs they encompass different types of periodic factors in a
word but to a lesser extent.

A *cubic run* in a word $x$ is a maximal periodicity in $x$
whose length is at least three times its period.
More accurately, it is an interval $[i\dd j]$ of positions on $x$ whose
associated factor $u=x[i\dd j]$ satisfies $|u|\geq 3\per(u)$ and that
is not extensible to the left nor to the right with the same period.

We consider an ordering $\lt$ on the alphabet and define special positions
of a run $[i\dd j]$ in $x$ as follows.
Let $p$ be the period of $x[i\dd j]$ and let $w$ be the alphabetically
smallest conjugate (rotation) of $x[i\dd i+p-1]$.
Then $k$ is a special position of the run if $x[i\dd j]$ contains a square
$ww$ centred at $k$.
Special positions are shown in boldface in the above picture.

Show that a cubic run has at least one special position and that two
different cubic runs share no special position.

Use the fact that the smallest conjugate of a primitive word, a Lyndon
word, is border free.

Show both that the number of cubic runs in a word of length $n$ is smaller
than $n/2$ and that, for infinitely many $n$, it is at least $0.4n$.

Consider the inverse alphabet ordering $\lt^{-1}$ and count cubic runs in
words $x_m=(u^2\sa{a}^3v^2\sa{b}^3w^2\sa{c}^3)^m$, where
$u=\sa{a}^3\sa{b}^3$, $v=\sa{b}^3\sa{c}^3$ and $w=\sa{c}^3\sa{a}^3$.

## References

M. Crochemore, C. S. Iliopoulos, M. Kubica, J. Radoszewski, W. Rytter,
and T. Walen. On the maximal number of cubic runs in a string. In
A. Dediu, H. Fernau, and C. Martín-Vide, editors, *Language and Automata
Theory and Applications, 4th International Conference, LATA
2010, Trier, Germany, May 24-28, 2010. Proceedings*, volume 6031 of
Lecture Notes in Computer Science, pages 227-238. Springer, 2010.
[86] M. Crochemore, C. S. Iliopoulos, M. Kubica, J. Radoszewski, W. Rytter,
and T. Walen. The maximal number of cubic runs in a word. *J. Comput.
Syst. Sci.*, **78**(6):1828-1836, 2012.
T. Harju and T. Kärki. On the number of frames in binary words. *Theor.
Comput. Sci.*, **412**(39):5276-5284, 2011.