CLR cover
Previous page

Ordering

Next page

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.