# 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

with and . Some authors reverse the order of the inequalities.

## Chen–Fox–Lyndon theorem[edit]

A Lyndon word over a totally ordered alphabet *A* is a word which 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[edit]

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

A **bisection** of a free monoid is a factorisation with just two classes *X*_{0}, *X*_{1}.^{[5]}

Examples:

*A*= {*a*,*b*},*X*_{0}= {*a*^{*}*b*},*X*_{1}= {*a*}.

If *X*, *Y* are disjoint sets of non-empty words, then (*X*,*Y*) is a bisection of *A** if and only if^{[6]}

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

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

## References[edit]

**^**Lothaire (1997) p.64**^**Lothaire (1997) p.67**^**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..**^**Guy Melançon, (1992) "Combinatorics of Hall trees and Hall words",*Journal of Combinatoric Theory*,**59A**(2) pp. 285–308.**^**Lothaire (1997) p.68**^**Lothaire (1997) p.69**^**Lothaire (1997) p.71**^**Lothaire (1997) p.92

- Lothaire, M. (1997),
*Combinatorics on words*, Encyclopedia of Mathematics and Its Applications,**17**, Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (2nd ed.), Cambridge University Press, ISBN 0-521-59924-5, Zbl 0874.20040