Monoid factorisation

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} \cdots x_{i_n} \

with x_{i_j} \in X_{i_j} and i_1 \ge i_2 \ge \ldots \ge i_n.

Chen–Fox–Lyndon theorem

A Lyndon word over a totally ordered alphabet A is a word which 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]

Bisection

A bisection of a free monoid is a factorisation with just two classes X0, X1.[4]

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

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

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 holds:

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. Lothaire (1997) p.68
  5. Lothaire (1997) p.69
  6. Lothaire (1997) p.71
  7. Lothaire (1997) p.92
This article is issued from Wikipedia - version of the Monday, May 05, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.