# 9.48 LyndonWordΒΆ

Initialisations

a:Symbol :='a


 a

Type: Symbol

b:Symbol :='b


 b

Type: Symbol

c:Symbol :='c


 c

Type: Symbol

lword:= LyndonWord(Symbol)


 LyndonWordSymbol

Type: Domain

magma := Magma(Symbol)


 MagmaSymbol

Type: Domain

word := OrderedFreeMonoid(Symbol)


 OrderedFreeMonoidSymbol

Type: Domain

All Lyndon words with a, b, c to order 3

LyndonWordsList1([a,b,c],3)$lword    [[[a],[b],[c]],[[ab],[ac],[bc]],[[a2b],[a2c],[ab2],[abc],[acb],[ac2],[b2c],[bc2]]] Type: OneDimensionalArray List LyndonWord Symbol All Lyndon words of with a, b, c to order 3 in flat list LyndonWordsList([a,b,c],3)$lword


 [[a],[b],[c],[ab],[ac],[bc],[a2b],[a2c],[ab2],[abc],[acb],[ac2],[b2c],[bc2]]

Type: List LyndonWord Symbol

All Lyndon words of with a, b to order 5

lw := LyndonWordsList([a,b],5)$lword    [[a],[b],[ab],[a2b],[ab2],[a3b],[a2b2],[ab3],[a4b],[a3b2],[a2bab],[a2b3],[abab2],[ab4]] Type: List LyndonWord Symbol w1 : word := lw.4 :: word    a2b Type: OrderedFreeMonoid Symbol w2 : word := lw.5 :: word    ab2 Type: OrderedFreeMonoid Symbol Let’s try factoring factor(a::word)$lword


 [[a]]

Type: List LyndonWord Symbol

factor(w1*w2)$lword    [[a2bab2]] Type: List LyndonWord Symbol factor(w2*w2)$lword


 [[ab2],[ab2]]

Type: List LyndonWord Symbol

factor(w2*w1)$lword    [[ab2],[a2b]] Type: List LyndonWord Symbol Checks and coercions lyndon?(w1)$lword


 true

Type: Boolean

lyndon?(w1*w2)$lword    true Type: Boolean lyndon?(w2*w1)$lword


 false

Type: Boolean

lyndonIfCan(w1)$lword    [a2b] Type: Union(LyndonWord Symbol,...) lyndonIfCan(w2*w1)$lword


 “failed”

Type: Union(“failed”,...)

lyndon(w1)$lword    [a2b] Type: LyndonWord Symbol lyndon(w1*w2)$lword


 [a2bab2]

Type: LyndonWord Symbol