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

Hall words[]

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

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

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

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

See also[]

• Sesquipower

References[]

• 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