## Example

\(
\def\sa#1{\tt{#1}}
\def\strl{\mathrm{\;\lt\lt \;}} % Strictly less, not prefix
\)

$\sa{ababb}\lt \sa{abba}\lt \sa{abbaab}$ when considering $\sa a\lt \sa b$ and more
generally the natural ordering on the alphabet $\mathbf{A}$.

The word $\sa{aababaabaaba}$ factorises as
$\sa{aabab}\cdot\sa{aab}\cdot\sa{aab}\cdot\sa{a}$, where $\sa{aabab}$,
$\sa{aab}$ and $\sa{a}$ are Lyndon words.

The word $\sa{aabaab}=\sa{aab}^2$ is a necklace
without being a Lyndon word.

#
Ordering

Some algorithms benefit from the existence of an ordering on the alphabet,
denoted by $\leq$.
The ordering induces the *lexicographic ordering*
or *alphabetic ordering* on words as follows.
Like the alphabet ordering, it is denoted by $\leq$.
For $x,y\in A^*$, $x\leq y$ if and only if
either $x$ is a prefix of $y$ or $x$ and $y$ can be decomposed as $x=uav$ and
$y=ubw$ for words $u$, $v$ and $w$, letters $a$ and $b$, with $a\lt b$.

We say that $x$ is
*strongly less* than $y$, denoted by $x \strl y$, when $x\leq y$
but $x$ is not a prefix of $y$.
Note that $x\strl y$ implies $xu\strl yv$ for
any words $u$ and $v$.

Concepts of *Lyndon words* and of *necklaces*
are built from the lexicographic ordering.

A Lyndon word $x$ is a primitive word that is the smallest among its
conjugates.
Equivalently but not entirely obvious, $x$ is smaller than all
its proper non-empty suffixes, and as such is also called a *self-minimal
word*.
As a consequence, $x$ is border free.
It is known that any non-empty word $w$ factorises uniquely into
$x_0x_1\cdots x_k$, where $x_i$s are Lyndon
words and $x_0 \geq x_1 \geq \cdots \geq x_k$.

A necklace or *minimal word* is a word that is the smallest in its
conjugacy class.
It is an (integer) power of a Lyndon word.
A Lyndon word is a necklace but a necklace
is not necessarily a Lyndon word.