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–FoxLyndon 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

with and . 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 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.[3]

Hall words

The Hall set provides a factorization.[4] 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.[5]

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 if[6]

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.[7]

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.[8]

See also

References

  1. Lothaire (1997) p.64
  2. Lothaire (1997) p.67
  3. 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..
  4. Guy Melançon, (1992) "Combinatorics of Hall trees and Hall words", Journal of Combinatoric Theory, 59A(2) pp. 285–308.
  5. Lothaire (1997) p.68
  6. Lothaire (1997) p.69
  7. Lothaire (1997) p.71
  8. Lothaire (1997) p.92
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.