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.

125 Problems in Text Algorithms

Example

Problem 113: Primitivity Test for Unary Extensions

References