Monoid factorisation

A Lyndon word over a totally ordered alphabet A is a word that is lexicographically less than all its rotations. 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 to be the singleton set for each Lyndon word , with the index set L of Lyndon words ordered lexicographically, we obtain a factorisation of . Such a factorisation can be found in linear time and constant space by Duval's algorithm. The algorithm 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 ==Hall words==

The Hall set provides a factorization. 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. Examples: :{{math|1=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 if and only if :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. ==Schützenberger theorem==

This theorem states that a sequence Xi of subsets of forms a factorisation if and only if two of the following three statements hold: • Every element of has at least one expression in the required form; • Every element of has at most one expression in the required form; • Each conjugate class C meets just one of the monoids and the elements of C in Mi are conjugate in Mi. ==See also==