LyndonWord VarSetΒΆ

xlpoly.spad line 141

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 RetractableTo VarSet
factor: FreeMonoid VarSet -> List %
factor(x) returns the decreasing factorization into Lyndon words.
hash: % -> SingleInteger
from SetCategory
hashUpdate!: (HashState, %) -> HashState
from SetCategory
latex: % -> String
from SetCategory
left: % -> %
left(x) returns left subtree of x or error if retractable? <l–lyndon-word_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 -> %
lyndon(w) convert w into a Lyndon word, error if w is not a Lyndon word.
lyndon?: FreeMonoid VarSet -> Boolean
lyndon?(w) test if w is 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? <l–lyndon-word_retractable?>`(``x`) is true.
smaller?: (%, %) -> Boolean
from Comparable
varList: % -> List VarSet
varList(x) returns the list of distinct entries of x.

BasicType

CoercibleTo OutputForm

Comparable

OrderedSet

PartialOrder

RetractableTo VarSet

SetCategory