xlpoly.spad line 141 [edit on github]
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).
LyndonWordsList(vl, n) returns the list of Lyndon words over the alphabet vl, up to order n.
LyndonWordsList1(vl, n) returns an array of lists of Lyndon words over the alphabet vl, up to order n.
coerce(x) returns the element of FreeMagma(VarSet) corresponding to x.
coerce(x) returns the element of FreeMonoid(VarSet) corresponding to x.
factor(x) returns the decreasing factorization into Lyndon words.
left(x) returns left subtree of x or error if retractable?(x) is true.
length(x) returns the number of entries in x.
lexico(x, y) returns true iff x is smaller than y w.r.t. the lexicographical ordering induced by VarSet.
lyndon(w) convert w into a Lyndon word, error if w is not a Lyndon word.
lyndon?(w) test if w is a Lyndon word.
lyndonIfCan(w) convert w into a Lyndon word.
retractable?(x) tests if x is a tree with only one entry.
right(x) returns right subtree of x or error if retractable?(x) is true.
varList(x) returns the list of distinct entries of x.
RetractableTo(VarSet)
CoercibleFrom(VarSet)