/usr/share/axiom-20170501/src/algebra/LWORD.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 | )abbrev domain LWORD LyndonWord
++ Author: Michel Petitot (petitot@lifl.fr).
++ Date Created: 91
++ Date Last Updated: 7 Juillet 92
++ Fix History: compilation v 2.1 le 13 dec 98
++ References:
++ Free Lie Algebras by C. Reutenauer (Oxford science publications).
++ Description:
++ 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 \axiom{a} and \axiom{b} are two Lyndon words such that \axiom{a < b}
++ holds w.r.t lexicographical ordering then \axiom{a*b} is a Lyndon word.
++ Parenthesized Lyndon words can be generated from symbols by using the
++ following rule:\br
++ \axiom{[[a,b],c]} is a Lyndon word iff \axiom{a*b < c <= b} holds.\br
++ Lyndon words are internally represented by binary trees using the
++ \spadtype{Magma} domain constructor.
++ Two ordering are provided: lexicographic and
++ length-lexicographic.
LyndonWord(VarSet) : SIG == CODE where
VarSet : OrderedSet
OFMON ==> OrderedFreeMonoid(VarSet)
PI ==> PositiveInteger
NNI ==> NonNegativeInteger
I ==> Integer
OF ==> OutputForm
ARRAY1==> OneDimensionalArray
SIG ==> Join(OrderedSet,RetractableTo VarSet) with
retractable? : $ -> Boolean
++ \axiom{retractable?(x)} tests if \axiom{x} is a tree
++ with only one entry.
left : $ -> $
++ \axiom{left(x)} returns left subtree of \axiom{x} or
++ error if retractable?(x) is true.
right : $ -> $
++ \axiom{right(x)} returns right subtree of \axiom{x} or
++ error if retractable?(x) is true.
length : $ -> PI
++ \axiom{length(x)} returns the number of entries in \axiom{x}.
lexico : ($,$) -> Boolean
++ \axiom{lexico(x,y)} returns \axiom{true} iff \axiom{x} is smaller
++ than \axiom{y} w.r.t. the lexicographical ordering induced by
++ \axiom{VarSet}.
coerce : $ -> OFMON
++ \axiom{coerce(x)} returns the element of
++ \axiomType{OrderedFreeMonoid}(VarSet)
++ corresponding to \axiom{x}.
coerce : $ -> Magma VarSet
++ \axiom{coerce(x)} returns the element of \axiomType{Magma}(VarSet)
++ corresponding to \axiom{x}.
factor : OFMON -> List $
++ \axiom{factor(x)} returns the decreasing factorization into
++ Lyndon words.
lyndon? : OFMON -> Boolean
++ \axiom{lyndon?(w)} test if \axiom{w} is a Lyndon word.
lyndon : OFMON -> $
++ \axiom{lyndon(w)} convert \axiom{w} into a Lyndon word,
++ error if \axiom{w} is not a Lyndon word.
lyndonIfCan : OFMON -> Union($, "failed")
++ \axiom{lyndonIfCan(w)} convert \axiom{w} into a Lyndon word.
varList : $ -> List VarSet
++ \axiom{varList(x)} returns the list of distinct entries of \axiom{x}
LyndonWordsList1 : (List VarSet, PI) -> ARRAY1 List $
++ \axiom{LyndonWordsList1(vl, n)} returns an array of lists of Lyndon
++ words over the alphabet \axiom{vl}, up to order \axiom{n}.
LyndonWordsList : (List VarSet, PI) -> List $
++ \axiom{LyndonWordsList(vl, n)} returns the list of Lyndon
++ words over the alphabet \axiom{vl}, up to order \axiom{n}.
CODE ==> Magma(VarSet) add
-- Representation
Rep:= Magma(VarSet)
-- Fonctions locales
LetterList : OFMON -> List VarSet
factor1 : (List $, $, List $) -> List $
-- Definitions
lyndon? w ==
w = 1$OFMON => false
f: OFMON := rest w
while f ^= 1$OFMON repeat
not lexico(w,f) => return false
f := rest f
true
lyndonIfCan w ==
l: List $ := factor w
# l = 1 => first l
"failed"
lyndon w ==
l: List $ := factor w
# l = 1 => first l
error "This word is not a Lyndon word"
LetterList w ==
w = 1 => []
cons(first w , LetterList rest w)
factor1 (gauche, x, droite) ==
g: List $ := gauche; d: List $ := droite
while not null g repeat ++ (l in g or l=x) et u in d
lexico( g.first , x ) => ++ => right(l) >= u
x := g.first *$Rep x -- crochetage
null(d) => g := rest g
g := cons( x, rest g) -- mouvement a droite
x := first d
d := rest d
d := cons( x , d) -- mouvement a gauche
x := first g
g := rest g
return cons(x, d)
factor w ==
w = 1 => []
l : List $ := reverse [ u::$ for u in LetterList w]
factor1( rest l, first l , [] )
x < y == -- lexicographique par longueur
lx,ly: PI
lx:= length x ; ly:= length y
lx = ly => lexico(x,y)
lx < ly
coerce(x:$):OF == bracket(x::OFMON::OF)
coerce(x:$):Magma VarSet == x::Rep
LyndonWordsList1 (vl,n) == -- a ameliorer !!!!!!!!!!!
null vl => error "empty list"
base: ARRAY1 List $ := new(n::I::NNI ,[])
-- mots de longueur 1
lbase1:List $ := [w::$ for w in sort(vl)]
base.1 := lbase1
-- calcul des mots de longueur ll
for ll in 2..n:I repeat
lbase1 := []
for a in base(1) repeat -- lettre + mot
for b in base(ll-1) repeat
if lexico(a,b) then lbase1:=cons(a*b,lbase1)
for i in 2..ll-1 repeat -- mot + mot
for a in base(i) repeat
for b in base(ll-i) repeat
if lexico(a,b) and (lexico(b,right a) or b = right a )
then lbase1:=cons(a*b,lbase1)
base(ll):= sort_!(lexico, lbase1)
return base
LyndonWordsList (vl,n) ==
v:ARRAY1 List $ := LyndonWordsList1(vl,n)
"append"/ [v.i for i in 1..n]
|