print(` Version of Feb. 27, 1997`): print(`This is NAIVE, A Maple package`): print(`that implements the Naive approach to problems that the`): print(` Goulden-Jackson Cluster method handles.`): print(`Written by John Noonan and Doron Zeilberger.`): lprint(``): print(`It is one of the packages accompanying Noonan and Zeilberger's `): print(`article: "The Goulden-Jackson Cluster Method: Extensions,`): print(`Applications, and Implementations", where the method`): print(`is explained in detail, and then extended and generalized in`): print(`various directions. `): print(`The present package contains very slow algorithm`): print(`and its main function is to test the other packages`): print(`Of course it computes Phi_R of the Noonan-Zeilberger paper`): print(`which is of great theoretical interest`): lprint(``): print(`The paper, and the packages, including the present one`): print(`is available from http://www.math.temple.edu/~zeilberg`): lprint(``): print(`For general help, and a list of the available functions,`): print(` type "ezra();". For specific help type "ezra(procedure_name)" `): lprint(``): ezra:=proc() if args=NULL then print(`NAIVE`): print(`A Maple package that implements the naive approach to`): print(`problems solved by the Goulden-Jackson Cluster method`): print(` for finding generating functions and series expansions`): print(`for the number of words avoiding a prescribed, finite, set of`): print(`"mistakes". Contains Procedures `): print(`Naivegf,NaivegfDetail, Naives, Naivest,NaivestDetail, PhiR `): print(` For specific help type "ezra(procedure_name)" `): fi: if nops([args])=1 and op(1,[args])=`NaivegfDetail` then print(`NaivegfDetail(alphabet,MISTAKES,x,t): Weight enumerator`): print(`of all words where the weight of a word is the product`): print(`of the weights of its letters times the product of t[w]`): print(`for every occurence of a factor w in MISTAKES`): fi: if nops([args])=1 and op(1,[args])=`Naivegf` then print(`Warning: Extremely slow method, the Naive method`): lprint(``): print(`Naivegf(alphabet,MISTAKES,x,t), using the NAIVE method`): print(` finds the generating function`): print(`F(x[l_1],x[l_2],...,x[l_r];t), the weight enumerator of `): print(`of all words in the alphabet=[l_1,..,l_r], where the`): print(`the weight of a word is the product of x[its letters] times`): print(`t^(#number of factors that belong to the list MISTAKES`): print(`For example to get the g.f. for the set of words`): print(`in the alphabet {1,2,3}, avoiding 123,231,312, type`): print(` type Naivegf({1,2,3},{[1,2,3],[2,3,1],[3,1,2]},x,t)`): fi: if nops([args])=1 and op(1,[args])=`Naivest` then print(`Naive method!, very slow!`): lprint(``): print(`Naivest(alphabet,MISTAKES,s,t) finds the generating function`): print(`F(s,t), the weight enumerator of `): print(`of all words in the alphabet={l_1,..,l_r}, where the`): print(`the weight of a word is s^(length) times `): print(`t^(#number of factors that belong to the list MISTAKES`): lprint(``): print(`For example to get the g.f. for the set of words`): print(`in the alphabet {1,2,3}, with bad words: 123,231,312, type`): print(` type Naivest({1,2,3} ,{[1,2,3],[2,3,1],[3,1,2]},s,t)`): lprint(``): print(`Warning: VERY SLOW and memory-consuming, only for checking`): print(`and theoretical use!`): fi: if nops([args])=1 and op(1,[args])=`NaivestDetail` then print(`Naive method!, very slow!`): lprint(``): print(`NaivestDetail(alphabet,MISTAKES,s,t) finds the generating function`): print(`F(s,t[mistakes]), the weight enumerator of `): print(`of all words in the alphabet={l_1,..,l_r}, where the`): print(`the weight of a word is s^(length) times `): print(`product of t[w], (w is a factor of the word and w belongs to MISTAKES`): print(`For example to get the g.f. for the set of words`): print(`in the alphabet {1,2,3}, with bad words 123,231,312, type`): print(` type Naivest({1,2,3} ,{[1,2,3],[2,3,1],[3,1,2]},s,t)`): lprint(``): print(`Warning: VERY SLOW and memory-consuming, only for checking`): print(`and theoretical use!`): fi: if nops([args])=1 and op(1,[args])=`Naives` then print(`Naive method!, very slow!`): lprint(``): print(`Naives(alphabet,MISTAKES,s) finds the generating function`): print(`g(s), is the g.f. sum(a[i]*s^i,i=0..infty) `): print(`where a[i]:=number of words of length i without any mistakes`): print(`from MISTAKES`): print(`For example to get the g.f. for a_n:=number of words of length n`): print(`in the alphabet {1,2,3}, avoiding 123,231,312, type`): print(` type Naives({1,2,3},{[1,2,3],[2,3,1],[3,1,2]},s)`): lprint(``): print(`Warning: VERY SLOW and memory-consuming, only for checking`): print(`and theoretical use!`): fi: if nops([args])=1 and op(1,[args])=`PhiR` then lprint(``): print(`PhiR(Alphabet,R,x)`): print(`Computes the function Phi_R(x) with respect to a given`): print(`alphabet, as described in the Noonan-Zeilberger paper`): print(`i.e. it is the weight enumerator of all words in the`): print(`alphabet where the weight of a word is the product of`): print(`x[w] where w ranges over all factors of length <=R`): fi: end: mishkalna:=proc(v,R,x) local i,j,gu: gu:=1: for i from 1 to nops(v) do for j from i to min(i+R-1,nops(v)) do gu:=gu*x[op(i..j,v)]: od: od: gu: end: AllWordsuptok:=proc(Alphabet,k) local i,gu: gu:={}: for i from 1 to k do gu:=gu union AllWordsk(Alphabet,i): od: gu: end: AllWordsk:=proc(Alphabet,k) local j,gu,i,mu,mila: if k=0 then RETURN({[]}): fi: mu:=AllWordsk(Alphabet,k-1): gu:={}: for i from 1 to nops(mu) do mila:=op(i,mu): for j from 1 to nops(Alphabet) do gu:=gu union {[op(mila),op(j,Alphabet)]}: od: od: gu: end: PhiR:=proc(Alphabet1,R,x) local eq,var,i,gu,j,ot,Alphabet,Sof,eq1,pro,mila,PHI,mu,r: if not type(Alphabet1,set) or type(Alphabet1,list) then ERROR(`The first argument of Naive should be a set or list`): fi: if type(Alphabet1,list) then Alphabet:=convert(Alphabet1,set) else Alphabet:=Alphabet1: fi: if not type(R,integer) or R<0 then ERROR(`The second argument should be a non-negative integer`): fi: gu:=AllWordsk(Alphabet,R): eq:={}: var:={}: for i from 1 to nops(gu) do mila:=op(i,gu): var:=var union {Sof[op(mila)]}: eq1:=Sof[op(mila)]-mishkalna(mila,R,x): for j from 1 to nops(Alphabet) do ot:=op(j,Alphabet): pro:=x[ot,op(mila)]: for r from 1 to R do pro:=pro*x[op(R-r+1..R,mila)]: od: if R>0 then eq1:=eq1-pro*Sof[ot,op(1..R-1,mila)]: else eq1:=eq1-pro*Sof[]: fi: od: eq:=eq union {eq1}: od: var:=solve(eq,var): if var=NULL then ERROR(`Something is wrong; No solution, please report to the authors`): fi: PHI:=0: for r from 0 to R-1 do mu:=AllWordsk(Alphabet,r): for i from 1 to nops(mu) do mila:=op(i,mu): PHI:=PHI+mishkalna(mila,nops(mila),x): od: od: for i from 1 to nops(gu) do mila:=op(i,gu): PHI:=PHI+subs(var,Sof[op(mila)]): od: normal(PHI): end: Naivegf:=proc(alphabet,MISTAKES,x,t) local R,kha,PHI,mu,i, mila: R:=0: for i from 1 to nops(MISTAKES) do kha:=nops(op(i,MISTAKES)): if kha>R then R:=kha: fi: od: PHI:=PhiR(alphabet,R-1,x): mu:=AllWordsuptok(alphabet,R): for i from 1 to nops(mu) do mila:=op(i,mu): if member(mila,MISTAKES) then PHI:=subs(x[op(mila)]=t,PHI): else if nops(mila)>1 then PHI:=subs(x[op(mila)]=1,PHI): fi: fi: od: PHI: end: Naivest:=proc(alphabet,MISTAKES,s,t) local R,kha,PHI,mu,i, mila, x: R:=0: for i from 1 to nops(MISTAKES) do kha:=nops(op(i,MISTAKES)): if kha>R then R:=kha: fi: od: PHI:=PhiR(alphabet,R-1,x): mu:=AllWordsuptok(alphabet,R): for i from 1 to nops(mu) do mila:=op(i,mu): if nops(mila)=1 then if member(mila,MISTAKES) then PHI:=subs(x[op(mila)]=s*t,PHI): else PHI:=subs(x[op(mila)]=s,PHI): fi: fi: if member(mila,MISTAKES) then PHI:=subs(x[op(mila)]=t,PHI): else PHI:=subs(x[op(mila)]=1,PHI): fi: od: PHI: end: Naives:=proc(alphabet,MISTAKES,s) local t: subs(t=0,Naivest(alphabet,MISTAKES,s,t)): normal("): end: #NaivegfDetail(alphabet,MISTAKES,x,t): Weight enumerator #of all words where the weight of a word is the product #of the weights of its letters times the product of t[w] #for every occurence of a factor w in MISTAKES NaivegfDetail:=proc(alphabet,MISTAKES,x,t) local R,kha,PHI,mu,i, mila: R:=0: for i from 1 to nops(MISTAKES) do kha:=nops(op(i,MISTAKES)): if kha>R then R:=kha: fi: od: PHI:=PhiR(alphabet,R-1,x): mu:=AllWordsuptok(alphabet,R): for i from 1 to nops(mu) do mila:=op(i,mu): if member(mila,MISTAKES) then PHI:=subs(x[op(mila)]=t[op(mila)],PHI): else if nops(mila)>1 then PHI:=subs(x[op(mila)]=1,PHI): fi: fi: od: PHI: end: NaivestDetail:=proc(alphabet,MISTAKES,s,t) local R,kha,PHI,mu,i, mila, x: R:=0: for i from 1 to nops(MISTAKES) do kha:=nops(op(i,MISTAKES)): if kha>R then R:=kha: fi: od: PHI:=PhiR(alphabet,R-1,x): mu:=AllWordsuptok(alphabet,R): for i from 1 to nops(mu) do mila:=op(i,mu): if nops(mila)=1 then PHI:=subs(x[op(mila)]=s,PHI): fi: if member(mila,MISTAKES) then PHI:=subs(x[op(mila)]=t[op(mila)],PHI): else PHI:=subs(x[op(mila)]=1,PHI): fi: od: PHI: end: