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.
Let A∗ be the free monoid on an alphabet A. Let Xi 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 ⋯ x i n {\displaystyle w=x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}\ }with x i j ∈ X i j {\displaystyle x_{i_{j}}\in X_{i_{j}}} and i 1 ≥ i 2 ≥ … ≥ i n {\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 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 algorithm4 in Python code is:
def chen_fox_lyndon_factorization(s: list[int]) -> list[int]: """Monoid factorisation using the Chen–Fox–Lyndon theorem. Args: s: a list of integers Returns: a list of integers """ n = len(s) factorization = [] i = 0 while i < n: j, k = i + 1, i while j < n and s[k] <= s[j]: if s[k] < s[j]: k = i else: k += 1 j += 1 while i <= k: factorization.append(s[i:i + j - k]) i += j - k return factorizationHall words
The Hall set provides a factorization.5 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 X0, X1.6
Examples:
A = {a,b}, X0 = {A∗b}, X1 = {a}.If X, Y are disjoint sets of non-empty words, then (X,Y) is a bisection of A∗ if and only if7
Y X ∪ A = X ∪ Y . {\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.8
Schützenberger theorem
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:
- Every element of A∗ has at least one expression in the required form;
- Every element of A∗ has at most one expression in the required form;
- Each conjugate class C meets just one of the monoids Mi = Xi∗ and the elements of C in Mi are conjugate in Mi.9
See also
- 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
References
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.. /wiki/Doi_(identifier) ↩
"Lyndon factorization - Algorithms for Competitive Programming". cp-algorithms.com. Retrieved 2024-01-30. https://cp-algorithms.com/string/lyndon_factorization.html ↩
Guy Melançon, (1992) "Combinatorics of Hall trees and Hall words", Journal of Combinatoric Theory, 59A(2) pp. 285–308. https://core.ac.uk/download/pdf/82581798.pdf ↩
Lothaire (1997) p.68 ↩
Lothaire (1997) p.69 ↩
Lothaire (1997) p.71 ↩
Lothaire (1997) p.92 ↩