Monoid factorisation

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 X_l 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:

def chen_fox_lyndon_factorization(s: list[int]) -> list[int]: """Monoid factorisation using the Chen-Fox-Lyndon theorem. Args: s: a list of integers Returns: a list of integers """ n = len(s) factorization = [] i = 0 while i < n: j, k = i + 1, i while j < n and s[k] <= s[j]: if s[k] < s[j]: k = i else: k += 1 j += 1 while i <= k: factorization.append(s[i:i + j - k]) i += j - k return factorization

The Hall set provides a factorization. Indeed, Lyndon words are a special case of Hall words. The article on Hall words provides a sketch of all of the mechanisms needed to establish a proof of this factorization.

A bisection of a free monoid is a factorisation with just two classes X₀, X₁.

Examples:

A = {a,b}, X₀ = {A^∗b}, X₁ = {a}.

If X, Y are disjoint sets of non-empty words, then (X,Y) is a bisection of A^∗ if and only if

As a consequence, for any partition P, Q of A⁺ there is a unique bisection (X,Y) with X a subset of P and Y a subset of Q.

This theorem states that a sequence X_i of subsets of A^∗ forms a factorisation if and only if two of the following three statements hold:

• Every element of A^∗ has at least one expression in the required form;
• Every element of A^∗ has at most one expression in the required form;
• Each conjugate class C meets just one of the monoids M_i = X_i^∗ and the elements of C in M_i are conjugate in M_i.