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}