Example
\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\def\per{\mathit{per}}
\def\tail{\mathit{tail}}
\def\fib{\mathit{fib}}
\)
$\tail(\sa{abcd}) = \sa{abcd}$ because the associated words are
$u=\varepsilon$ and $v=\sa{abcd}$, $\tail(\sa{abaab})=\sa{a}$ because
$\sa{abaab}=(\sa{aba})^1\sa{ab}$ and $\tail(\sa{abaababa})=\sa{ab}$ because
$\sa{abaababa}=(\sa{abaab})^1\sa{aba}$.
The latter word is the Fibonacci word
$\fib_4$ and in general $\tail(\fib_n)=\fib_{n-3}$, for $n \geq 3$.
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.