Schützenberger Theorem

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 ''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_ x_ \cdots x_ \$

with $x_ \in X_$ and $i_1 \ge i_2 \ge \ldots \ge 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.Lothaire (1997) p.64 The Chen–Fox–Lyndon theorem states that every string may be formed in a unique way by concatenating a non-increasing sequence of Lyndon words. Hence taking ''X''_''l'' to be the singleton set for each Lyndon word ''l'', with the index set ''L'' of Lyndon words ordered lexicographically, we obtain a factorisation of ''A''^*.Lothaire (1997) p.67 Such a factorisation can be found in linear time..

Hall words

The Hall set provides a factorization.
Guy Melançon, (1992)
Combinatorics of Hall trees and Hall words
, ''Journal of Combinatoric Theory'', 59A(2) pp. 285–308.

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 ''X''₀, ''X''₁.Lothaire (1997) p.68

Examples:
:''A'' = , ''X''₀ = , ''X''₁ = .

If ''X'', ''Y'' are disjoint sets of non-empty words, then (''X'',''Y'') is a bisection of ''A''* if and only ifLothaire (1997) p.69
:$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''.Lothaire (1997) p.71

Schützenberger theorem

This theorem states that a sequence ''X''_''i'' 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 ''M''_''i'' = ''X''_''i''* and the elements of ''C'' in ''M''_''i'' are conjugate in ''M''_''i''.Lothaire (1997) p.92

See also

* Sesquipower

References

*{{Citation , last=Lothaire , first=M. , authorlink=M. Lothaire , others=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 , title=Combinatorics on words , edition=2nd , series=Encyclopedia of Mathematics and Its Applications , volume=17 , publisher=Cambridge University Press , year=1997 , isbn=0-521-59924-5 , zbl=0874.20040

Formal languages