go-v.orgcodex
Menu
Page tools

codex · Philosophy

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=xi1xi2⋯xin with xij∈Xij and i1≥i2≥…≥in. Some authors reverse the order of the inequalities.

Wikipedia contributors, "Monoid factorisation", Wikipedia, revision 1237911536, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex