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 ''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

:$w = x_ x_ \cdots x_ \$

with $x_ \in X_$ and $i_1 \ge i_2 \ge \ldots \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.Lothaire (1997) p.64 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 .Lothaire (1997) p.67 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 nt -> list nt
"""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 + j - k
i += j - k
return factorization

Hall words

The Hall set provides a factorization.
Guy Melançon, (1992)
Combinatorics of Hall trees and Hall words
, ''Journal of Combinatoric Theory'', 59A(2) pp. 285–308.

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''₁.Lothaire (1997) p.68

Examples:
:

If ''X'', ''Y'' are disjoint sets of non-empty words, then (''X'',''Y'') is a bisection of if and only ifLothaire (1997) p.69
:$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''.Lothaire (1997) p.71

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''.Lothaire (1997) p.92

See also

* Sesquipower

References

*{{Citation , last=Lothaire , first=M. , authorlink=M. Lothaire , others=Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J.-É.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, R.; Rota, G.-C. Foreword by Roger Lyndon , title=Combinatorics on words , edition=2nd , series=Encyclopedia of Mathematics and Its Applications , volume=17 , publisher=Cambridge University Press , year=1997 , isbn=0-521-59924-5 , zbl=0874.20040

Formal languages