From Wikipedia, the free encyclopedia
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 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
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[edit]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 algorithm[4] 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 factorization
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.
A bisection of a free monoid is a factorisation with just two classes X0, X1.[6]
Examples:
If X, Y are disjoint sets of non-empty words, then (X,Y) is a bisection of A∗ if and only if[7]
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[edit]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:
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4