Monoid factorisation

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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

Hall words[edit]

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

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

  • Every element of A* has at least one expression in the required form;[clarification needed]
  • 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][clarification needed]

See also[edit]

References[edit]

  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
  • Lothaire, M. (1997), Combinatorics on words, Encyclopedia of Mathematics and Its Applications, 17, Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (2nd ed.), Cambridge University Press, ISBN 0-521-59924-5, Zbl 0874.20040