Monoid factorisation
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a factorisation of a
free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...
is a sequence of
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
s 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 Lyndon may refer to: Places * Lyndon, Alberta, Canada * Lyndon, Rutland, East Midlands, England * Lyndon, Solihull, West Midlands, England United States * Lyndon, Illinois * Lyndon, Kansas * Lyndon, Kentucky * Lyndon, New York * Lyndon, Ohio * ...
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 In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...
on an alphabet ''A''. Let ''X''''i'' be a sequence of subsets of ''A''* indexed by a
totally ordered In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive ...
index set In mathematics, an index set is a set whose members label (or index) members of another set. For instance, if the elements of a set may be ''indexed'' or ''labeled'' by means of the elements of a set , then is an index set. The indexing consists ...
''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 In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...
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 In mathematics, a singleton, also known as a unit set or one-point set, is a set with exactly one element. For example, the set \ is a singleton whose single element is 0. Properties Within the framework of Zermelo–Fraenkel set theory, the ...
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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
..


Hall words

The
Hall set In mathematics, in the areas of group theory and combinatorics, Hall words provide a unique monoid factorisation of the free monoid. They are also totally ordered, and thus provide a total order on the monoid. This is analogous to the better-know ...
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 word In mathematics, in the areas of group theory and combinatorics, Hall words provide a unique monoid factorisation of the free monoid. They are also totally ordered, and thus provide a total order on the monoid. This is analogous to the better-know ...
s 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''0, ''X''1.Lothaire (1997) p.68 Examples: :''A'' = , ''X''0 = , ''X''1 = . If ''X'', ''Y'' are
disjoint sets In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A ...
of non-empty words, then (''X'',''Y'') is a bisection of ''A''*
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
Lothaire (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
monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoid ...
s ''M''''i'' = ''X''''i''* and the elements of ''C'' in ''M''''i'' are conjugate in ''M''''i''.Lothaire (1997) p.92


See also

*
Sesquipower In mathematics, a sesquipower or Zimin word is a string over an alphabet with identical prefix and suffix. Sesquipowers are unavoidable patterns, in the sense that all sufficiently long strings contain one. Formal definition Formally, let ''A'' b ...


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 Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer. Cambridge University Pr ...
, year=1997 , isbn=0-521-59924-5 , zbl=0874.20040 Formal languages