StringTools - Maple Programming Help

# Online Help

###### All Products    Maple    MapleSim

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)

 See Also

## Was this information helpful?

 Please add your Comment (Optional) E-mail Address (Optional) What is ? This question helps us to combat spam