Algorithms for the Lyndon Unique Maximal Factorization.

Abstract

Let $\mathrm{\Sigma }$ be a totally ordered set. We work on finite strings $b=b_1{b}_2\dots b_m$ of $b_i$ elements from $\mathrm{\Sigma }$. Such a $b$ is a lyn(Lyndon word) if $m\ge 1$, and $b$ is the unique first in lex(lexicographic order) among the $m$ rows of the $m\times m$ circulant matrix with $b$ as first row.

A classic result is that every string $b$ has a unique max factorization $umf(b)$ into Lyns , each Lyn of maximum possible size in $b$.

In 1983 J. P. Duval [6] published Algorithm 1, which finds $umf(b)$. It was studied in 1991 by A. Apostolico and M. Crochemore [1]. Then their work was studied in 1994 by J.W. Daykin, C.S. Iliopoulos, and W.F. Smyth [5].

Since Duval used a programming language, we start by giving a new simple account of his Algorithm 1. Then our Algorithm 2 given here modifies Duval’s Algorithm 1 to find $umf(a)$, when $a$ is a string $a=A_1{A}_2\dots A_p$ of Lyndon words $A_I$.

Our Algorithm 3 is also for a string $a=A_1{A}_2\dots A_p$ of Lyndon words $A_I$. It is completely different from Algorithms 1 and 2. It snakes right, left, right, and so on. It revealed the fact that Lyndon words have a special structure. We give an example where Algorithm 3 needs almost $2m$ tests; we think that is the most needed, but cannot give a rigorous proof.

We find interesting properties of Lyns, some of which may be new.