Monoid factorisation

In mathematics, a factorisation of a free monoid is a sequence of subsets of words with the property that every word in the free monoid can be written as a concatenation of elements drawn from the subsets. The Chen–Fox–Lyndon theorem states that the Lyndon words furnish a factorisation. The Schützenberger theorem relates the definition in terms of a multiplicative property to an additive property.

Let A∗ be the free monoid on an alphabet A. Let Xi be a sequence of subsets of A∗ indexed by a totally ordered index set I. A factorisation of a word w in A∗ is an expression

w

=

x

i

1

x

i

2

⋯

x

i

n

{\displaystyle w=x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}\ }

with

x

i

j

∈

X

i

j

{\displaystyle x_{i_{j}}\in X_{i_{j}}}

and

i

1

≥

i

2

≥

…

≥

i

n

{\displaystyle i_{1}\geq i_{2}\geq \ldots \geq i_{n}}

. Some authors reverse the order of the inequalities.

Chen–Fox–Lyndon theorem

A Lyndon word over a totally ordered alphabet A is a word that is lexicographically less than all its rotations. The Chen–Fox–Lyndon theorem states that every string may be formed in a unique way by concatenating a lexicographically non-increasing sequence of Lyndon words. Hence taking Xl to be the singleton set {l} for each Lyndon word l, with the index set L of Lyndon words ordered lexicographically, we obtain a factorisation of A∗. Such a factorisation can be found in linear time and constant space by Duval's algorithm. The algorithm in Python code is:

Hall words

The Hall set provides a factorization.