CLR cover
Previous problem

Problem 84: Cubic Runs

Next problem

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.

Cubic Runs

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.