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 be the free monoid on an alphabet A. Let Xi 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. 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. 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 -> list:
"""Monoid factorisation using the Chen–Fox–Lyndon theorem.
Args:
s: a list of integers
Returns:
a list of integers
"""
n = len
factorization =
i = 0
while i < n:
j, k = i + 1, i
while j < n and s <= s:
if s < s:
k = i
else:
k += 1
j += 1
while i <= k:
factorization.append
i += j - k
return factorization

Hall words

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.

Bisection

A bisection of a free monoid is a factorisation with just two classes X0, X1.
Examples:
If X, Y are disjoint sets of non-empty words, then is a bisection of if and only if
As a consequence, for any partition P, Q of A+ there is a unique bisection with X a subset of P and Y a subset of Q.

Schützenberger theorem

This theorem states that a sequence Xi 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 Mi are conjugate in Mi.