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.