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.Template:Clarify

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

$w=x_{i_1}{x}_{i_2}\cdots x_{i_n}$

with $x_{i_j}\in X_{i_j}$ and $i_1\ge i_2\ge \dots \ge 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 Template:Math to be the singleton set Template:Math for each Lyndon word Template:Mvar, with the index set L of Lyndon words ordered lexicographically, we obtain a factorisation of Template:Math. 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

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 X₀, X₁.

Examples:

Template:Math

If X, Y are disjoint sets of non-empty words, then (X,Y) is a bisection of Template:Math if and only if

$YX\cup A=X\cup Y.$

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.

Schützenberger theorem

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

• Every element of Template:Math has at least one expression in the required form;Template:Clarify
• Every element of Template:Math has at most one expression in the required form;
• Each conjugate class C meets just one of the monoids Template:Math and the elements of C in M_i are conjugate in M_i.Template:Clarify

See also

• Sesquipower

References

• Template:Citation