Monoid factorisation explained

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 be the free monoid on an alphabet A. Let X_i be a sequence of subsets of indexed by a totally ordered index set I. A factorisation of a word w in is an expression

with

and . 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.^[1] 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 to be the singleton set for each Lyndon word, with the index set L of Lyndon words ordered lexicographically, we obtain a factorisation of .^[2] Such a factorisation can be found in linear time and constant space by Duval's algorithm.^[3] The algorithm^[4] 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

Hall words

The Hall set provides a factorization.^[5] 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.

Bisection

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

Examples:

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

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.^[8]

Schützenberger theorem

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

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

See also

• Sesquipower

Notes and References

1. Lothaire (1997) p.64
2. Lothaire (1997) p.67
3. Duval . Jean-Pierre . 10.1016/0196-6774(83)90017-2 . 4 . Journal of Algorithms . 363–381 . Factorizing words over an ordered alphabet . 4 . 1983. .
4. Web site: Lyndon factorization - Algorithms for Competitive Programming . 2024-01-30 . cp-algorithms.com.
5. Guy Melançon, (1992) "Combinatorics of Hall trees and Hall words", Journal of Combinatoric Theory, 59A(2) pp. 285–308.
6. Lothaire (1997) p.68
7. Lothaire (1997) p.69
8. Lothaire (1997) p.71
9. Lothaire (1997) p.92