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.

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

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

with $x_{i_{j}}\in X_{i_{j}}$ and $i_{1}\geq i_{2}\geq \ldots \geq i_{n}$.

References

• Lothaire, M. (1997), Combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 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