CLR cover

Problem 113: Primitivity Test for Unary Extensions

A non-empty word $x$ can be decomposed as $x=(uv)^eu$ for two words $u$ and $v$ where $v$ is non-empty, $|uv|=\per(x)$ is the (smallest) period of $x$ and $e$ is a positive integer. We set $\tail(x)=v$ (not $u$).

The goal of the problem is to test whether $xa^k$ is primitive when only little is known about the word $x$.

Assume the only information on $x$ is Show how to answer in constant time if the word $xa^k$ is primitive, for an integer $k$ and a letter $a$.
$\tail(x)$ is an obvious candidate to extend $x$ to a non-primitive word.


  • W. Rytter. Two fast constructions of compact representations of binary words with given set of periods. Theor. Comput. Sci., 656:180-187, 2016.