Monoid factorisation

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a factorisation of a <a href="/facts/Free_monoid/h3nPVjqr">free monoid</a> is a sequence of <a href="/facts/Subset/SJGERmbA">subsets</a> 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–<a href="/facts/Ralph_Fox/GFlG3J5v">Fox</a>–<a href="/facts/Roger_Lyndon/ESCf6Rr3">Lyndon</a> theorem states that the <a href="/facts/Lyndon_word/ckrmLgXQ">Lyndon words</a> furnish a factorisation. The <a href="/facts/Marcel_Sch%25C3%25BCtzenberger/aF62Lo9H">Schützenberger</a> theorem relates the definition in terms of a multiplicative property to an additive property.
Let A∗ be the <a href="/facts/Free_monoid/h3nPVjqr">free monoid</a> on an alphabet A. Let Xi be a sequence of subsets of A∗ indexed by a <a href="/facts/Totally_ordered_set/xnTtmuYJ">totally ordered</a> <a href="/facts/Index_set/Jta7dIan">index set</a> I. A factorisation of a word w in A∗ is an expression

w
        =
        
          x
          
            
              i
              
                1
              
            
          
        
        
          x
          
            
              i
              
                2
              
            
          
        
        ⋯
        
          x
          
            
              i
              
                n
              
            
          
        
         
      
    
    {\displaystyle w=x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}\ }

with 
 
 
 
 
 x
 
 
 i
 
 j
 
 
 
 
 ∈
 
 X
 
 
 i
 
 j
 
 
 
 
 
 
 {\displaystyle x_{i_{j}}\in X_{i_{j}}}
 
 and 
 
 
 
 
 i
 
 1
 
 
 ≥
 
 i
 
 2
 
 
 ≥
 …
 ≥
 
 i
 
 n
 
 
 
 
 {\displaystyle i_{1}\geq i_{2}\geq \ldots \geq i_{n}}
 
. Some authors reverse the order of the inequalities.

Monoid factorisation open-in-new

Monoid factorisation