# 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
• $x$ is not unary (contains at least two distinct letters),
• $\tail(x)$ is not unary or $\tail(x) \in b^*$, for a letter $b$,
• $\ell=|\tail(x)|$.
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.

## References

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