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.^{[clarification needed]}

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

${\displaystyle w=x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}\ }$

with ${\displaystyle x_{i_{j}}\in X_{i_{j}}}$ and ${\displaystyle i_{1}\geq i_{2}\geq \ldots \geq 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.^[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 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^∗.^[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:

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

${\displaystyle 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.^[8]

Schützenberger theorem

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;^{[clarification needed]}
• 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.^{[9][clarification needed]}

See also

• Sesquipower

References

1. Lothaire (1997) p.64
2. Lothaire (1997) p.67
3. Duval, Jean-Pierre (1983). "Factorizing words over an ordered alphabet". Journal of Algorithms. 4 (4): 363–381. doi:10.1016/0196-6774(83)90017-2..
4. "Lyndon factorization - Algorithms for Competitive Programming". cp-algorithms.com. Retrieved 2024-01-30.
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

• Lothaire, M. (1997), Combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 17, 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 (2nd ed.), Cambridge University Press, ISBN 0-521-59924-5, Zbl 0874.20040