LyndonWord VarSet

xlpoly.spad line 141 [edit on github]

• VarSet: OrderedSet

Lyndon words over arbitrary (ordered) symbols: see Free Lie Algebras by C. Reutenauer (Oxford science publications). A Lyndon word is a word which is smaller than any of its right factors w.r.t. the pure lexicographical ordering. If a and b are two Lyndon words such that a < b holds w.r.t lexicographical ordering then a*b is a Lyndon word. Parenthesized Lyndon words can be generated from symbols by using the following rule: [[a, b], c] is a Lyndon word iff a*b < c <= b holds. Lyndon words are internally represented by binary trees using the FreeMagma domain constructor. Two ordering are provided: lexicographic and length-lexicographic. Author : Michel Petitot (petitot@lifl.fr).

<=: (%, %) -> Boolean

from PartialOrder

<: (%, %) -> Boolean

from PartialOrder

=: (%, %) -> Boolean

from BasicType

>=: (%, %) -> Boolean

from PartialOrder

>: (%, %) -> Boolean

from PartialOrder

~=: (%, %) -> Boolean

from BasicType

coerce: % -> FreeMagma VarSet

coerce(x) returns the element of FreeMagma(VarSet) corresponding to x.

coerce: % -> FreeMonoid VarSet

coerce(x) returns the element of FreeMonoid(VarSet) corresponding to x.

coerce: % -> OutputForm

from CoercibleTo OutputForm

coerce: VarSet -> %

from CoercibleFrom VarSet

factor: FreeMonoid VarSet -> List %

factor(x) returns the decreasing factorization into Lyndon words.

latex: % -> String

from SetCategory

left: % -> %

left(x) returns left subtree of x or error if retractable?(x) is true.

length: % -> PositiveInteger

length(x) returns the number of entries in x.

lexico: (%, %) -> Boolean

lexico(x, y) returns true iff x is smaller than y w.r.t. the lexicographical ordering induced by VarSet.

lyndon?: FreeMonoid VarSet -> Boolean

lyndon?(w) test if w is a Lyndon word.

lyndon: FreeMonoid VarSet -> %

lyndon(w) convert w into a Lyndon word, error if w is not a Lyndon word.

lyndonIfCan: FreeMonoid VarSet -> Union(%, failed)

lyndonIfCan(w) convert w into a Lyndon word.

LyndonWordsList1: (List VarSet, PositiveInteger) -> OneDimensionalArray List %

LyndonWordsList1(vl, n) returns an array of lists of Lyndon words over the alphabet vl, up to order n.

LyndonWordsList: (List VarSet, PositiveInteger) -> List %

LyndonWordsList(vl, n) returns the list of Lyndon words over the alphabet vl, up to order n.

max: (%, %) -> %

from OrderedSet

min: (%, %) -> %

from OrderedSet

retract: % -> VarSet

from RetractableTo VarSet

retractable?: % -> Boolean

retractable?(x) tests if x is a tree with only one entry.

retractIfCan: % -> Union(VarSet, failed)

from RetractableTo VarSet

right: % -> %

right(x) returns right subtree of x or error if retractable?(x) is true.

smaller?: (%, %) -> Boolean

from Comparable

varList: % -> List VarSet

varList(x) returns the list of distinct entries of x.

BasicType

CoercibleFrom VarSet

CoercibleTo OutputForm

Comparable

OrderedSet

PartialOrder

RetractableTo VarSet

SetCategory