LyndonWord examples

A function f in [0,1] is called acyclic if C(F) consists of n different objects. The canonical representative of the orbit of an acyclic function is usually called a Lyndon Word. If f is acyclic, then all elements in the orbit C(f) are acyclic as well, and we call C(f) an acyclic orbit.

Initialisations

a:Symbol :='a
  a
                          Type: Symbol

b:Symbol :='b
  b
                          Type: Symbol

c:Symbol :='c
  c
                          Type: Symbol

lword:= LyndonWord(Symbol)
  LyndonWord Symbol
                          Type: Domain

magma := Magma(Symbol)
  Magma Symbol
                          Type: Domain

word := OrderedFreeMonoid(Symbol)
  OrderedFreeMonoid Symbol
                          Type: Domain

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

LyndonWordsList1([a,b,c],3)$lword
 [[[a],[b],[c]], [[a b],[a c],[b c]],
     2     2       2                      2    2       2
  [[a b],[a c],[a b ],[a b c],[a c b],[a c ],[b c],[b c ]]]
                          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
                                        2      2        2
 [[a], [b], [c], [a b], [a c], [b c], [a b], [a c], [a b ], [a b c], [a c b],
      2     2        2
  [a c ], [b c], [b c ]]
                          Type: List LyndonWord Symbol

All Lyndon words of with a, b to order 5

lw := LyndonWordsList([a,b],5)$lword
                     2        2     3      2 2       3     4      3 2
 [[a], [b], [a b], [a b], [a b ], [a b], [a b ], [a b ], [a b], [a b ],
    2          2 3           2       4
  [a b a b], [a b ], [a b a b ], [a b ]]
                          Type: List LyndonWord Symbol

w1 : word := lw.4 :: word
   2
  a b
                           Type: OrderedFreeMonoid Symbol

w2 : word := lw.5 :: word
     2
  a b
                           Type: OrderedFreeMonoid Symbol

Let’s try factoring

factor(a::word)$lword
  [[a]]
                           Type: List LyndonWord Symbol

factor(w1*w2)$lword
     2     2
  [[a b a b ]]
                           Type: List LyndonWord Symbol

factor(w2*w2)$lword
       2      2
  [[a b ],[a b ]]
                           Type: List LyndonWord Symbol

factor(w2*w1)$lword
       2    2
  [[a b ],[a b]]
                           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
    2
  [a b]
                           Type: Union(LyndonWord Symbol,...)

lyndonIfCan(w2*w1)$lword
  "failed"
                           Type: Union("failed",...)

lyndon(w1)$lword
    2
  [a b]
                           Type: LyndonWord Symbol

lyndon(w1*w2)$lword
    2     2
  [a b a b ]
                           Type: LyndonWord Symbol

See Also:

• )show LyndonWord