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.
[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 Xl 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:The Hall set provides a factorization.
The article on Hall words provides a sketch of all of the mechanisms needed to establish a proof of this factorization.
[8] This theorem states that a sequence Xi of subsets of A∗ forms a factorisation if and only if two of the following three statements hold: