StringTools - Maple Programming Help

Home : Support : Online Help : Programming : Names and Strings : StringTools Package : Combinatorics on Words : StringTools/LyndonFactors

StringTools

 LyndonFactors
 compute the Lyndon factorization of a string

 Calling Sequence LyndonFactors( w )

Parameters

 w - Maple string

Description

 • The LyndonFactors(w) command produces the Lyndon factorization of the string w.
 • A word (string) w is a Lyndon word if it is aperiodic and is the lexicographically least member of its conjugacy class (which is the set of all rotations of w). Every word admits an unique factorization as a product (catenation) of a non-increasing sequence of Lyndon words, called its Lyndon factorization.

Examples

 > $\mathrm{with}\left(\mathrm{StringTools}\right):$
 > $\mathrm{LyndonFactors}\left("abc"\right)$
 $\left[{"abc"}\right]$ (1)
 > $\mathrm{LyndonFactors}\left("abcdedcccbabab"\right)$
 $\left[{"abcdedcccb"}{,}{"ab"}{,}{"ab"}\right]$ (2)
 > $\mathrm{LyndonFactors}\left(\mathrm{ThueMorse}\left(60\right)\right)$
 $\left[{"011"}{,}{"01"}{,}{"0011"}{,}{"00101101"}{,}{"0010110011010011"}{,}{"001011001101001011010011"}{,}{"001"}\right]$ (3)
 > $\mathrm{LyndonFactors}\left(\mathrm{Fibonacci}\left(8\right)\right)$
 $\left[{"01"}{,}{"00101"}{,}{"0010010100101"}{,}{"00100101"}{,}{"001"}{,}{"001"}\right]$ (4)