print(`Version of Nov. 22, 1996`):
lprint(``):
 
print(`This is SAW,  a Maple package that studies Self Avoiding Walks`):
print(` in a strip, in conjunction with the package DIKDUK `):
lprint(``):
print(` The most current versions of SAW  and DIKDUK are available on WWW at:`):
print(` 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(``):
 
read(DIKDUK): 
 
Ezra:=proc()
 
if args=NULL then
print(` SAW `):
print(`a Maple package that studies Self-Avoiding Walks in  strips`):
print(` used in conjunction with the package DIDKUK `):
lprint(``):
print(`For help with a specific procedure, type "Ezra(procedure_name);"`):
lprint(``):
print(`Contains procedures: `):
print(` rasawab , rasaw, Opts, Optsab, muav , muavab, SAW, SAWab `):
print(` SAWWab,LWWb, TrySAWr, TryLWr , gfSawabg, RASAWWab , RagfSawab01g `):
print(` RagfSawab01 `):
print(` gfSawab ,  gfLWWb , SAWrightab, SAWWrightab, gfSawrightab `):
fi:
 
 
if nops([args])=1 and op(1,[args])=`RagfSawab01g` then
print(`RagfSawab01g(r,t,N,GVUL): Assuming that the sets `):
print(`of SAWs restricted to the`):
print(`strip [0,1] is reduced r-Markovian, finds the generating function`):
print(`(where L and R are being kept track of) by guessing the grammar by`):
print(`picking sufficiently large corpuses drawn from random words`):
print(`N is the number of words in the smallest corpus`):
print(`GVUL is the limit, to make the program terminate`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`RagfSawab01` then
print(`RagfSawab01(r,t,N,GVUL): Assuming that the sets `):
print(`of SAWs restricted to the`):
print(`strip [0,1] is reduced r-Markovian, finds the generating function`):
print(`by guessing the grammar by`):
print(`picking sufficiently large corpuses drawn from random words`):
print(`N is the number of words in the smallest corpus`):
print(`GVUL is the limit, to make the program terminate`):
fi:
 
if nops([args])=1 and op(1,[args])=`RASAWWab` then
print(`RASAWWab(a,b): Generates a random word in the langauage`):
print(`of Self-Avoiding Walks in the strip [a,b] after it is translated`):
print(`to a sequence of edge-set describing vertical cross-sections with`):
print(`a second component describing whether it was to the left or right of`):
print(`the origin`):
fi:
 
if nops([args])=1 and op(1,[args])=`gfSawabra` then
print(`gfSawabra(a,b,r,t,K,n): Assuming that the sets of SAWs restricted`):
print(`to the strip [a,b] is reduced r-Markovian, finds the generating`):
print(` function by picking random elements and studying them`):
print(`K is the number of samples taken, it forms the grammar deduced from`):
print(`K samples, and then supplements another K samples, and if the`):
print(`grammar is identical proceeds, assuming that this is the grammar,`):
print(` otherwise it halts with an error message`):
fi:
 
if nops([args])=1 and op(1,[args])=`gfSawrightab` then
print(`gfSawrightab(a,b,r,t): Assuming that the sets of SAWs restricted `):
print(`to the strip [a,b], whose first visited point, after the origin is `):
print(`[1,0] and who  never visit the y-axix, except at the origin, `):
print(`is reduced r-Markovian, finds the generating function`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`SAWWrightab` then
print(`SAWWrightab(OREKH,a,b): the set of all 2D saws in the strip [a,b] `):
print(`whose first visited point, after the origin is [1,0] and that never`):
print(`touch the y-axis, and whose translation has length<=OREKH`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`SAWrightab` then
print(`SAWrightab(n,a,b): Gives the set of all self-avoiding walks of `):
print(`in the 2D square-lattice restricted to the strip [a,b], whose first`):
print(`n steps visited point (after the origin) is [1,0], and that never`):
print(`visit the y-axis except at the origin`):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`gfLWWb` then
print(`gfLWWb(b,r,t): Assuming that the sets of LWs restricted to the`):
print(`strip [0,b] is reduced r-Markovian, finds the generating function`):
fi:
 
if nops([args])=1 and op(1,[args])=`gfSawab` then
print(`gfSawab(a,b,r,t): Assuming that the sets of SAWs restricted to the`):
print(`strip [a,b] is reduced r-Markovian, finds the generating function`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`gfSawabg` then
 
print(`gfSawabg(a,b,r,t): Assuming that the sets of SAWs restricted to the`):
print(`strip [a,b] is reduced r-Markovian, finds the generating function`):
print(`(where L and R are being kept track of)`):
 
fi:
 
 
 
 
if nops([args])=1 and op(1,[args])=`LWWb` then
print(`LWWb(OREKH,b): the set of all 2D lattice walks in the strip [0,b] `):
print(`whose translation has length<=OREKH`):
fi:
 
if nops([args])=1 and op(1,[args])=`rasawab` then
 
print(`rasawab(n,a,b) finds a random self-avoiding walk of length n `):
print(`confined to the strip [a,b]. a should be a non-positive and`):
print(` b a non-negative integer`):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`rasaw` then
print(`rasaw(n) finds a random self-avoiding walk of length n `):
fi:
 
 
if nops([args])=1 and op(1,[args])=`Opts` then
print(`Opts(Walk): Given a saw Walk, find the set of options for`):
print(`for the next step`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`Optsab` then
print(`Optsab(Walk,a,b): Given a saw Walk in [a,b], find the set`):
print(`  of options for the next step`):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`muav` then
print(`muav(n,K) find the average number of options a random walk`):
print(`of n steps has to make the next step, using a random sample`):
print(`of K walks`):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`muavab` then
print(`muavab(n,a,b,K) find the average number of options a random walk`):
print(`of n steps, restricted to the strip [a,b]`):
print(` has to make the next step, using a random sample`):
print(`of K walks`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`SAW` then
print(`SAW(n): Gives the set of all self-avoiding walks of n steps`):
print(`in the 2D square-lattice`):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`SAWab` then
print(`SAWab(n,a,b): Gives the set of all self-avoiding walks of n steps`):
print(`in the 2D square-lattice, restricted to the strip [a,b]`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`SAWWab` then
print(`SAWWab(OREKH,a,b): the set of all 2D saws in the strip [a,b] `):
print(`whose translation has length<=OREKH`):
fi:
 
if nops([args])=1 and op(1,[args])=`TrySAWr` then
print(` TrySAWr(a,b,r) sees whether the language of SAWs in [a,b] `):
print(` is r-Markovian `):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`TryLWr` then
print(` TryLWr(b,r) sees whether the language of lattice walks in [0,b] `):
print(` is r-Markovian `):
fi:
 
 
 
end:
 
 
#rasawab(n,a,b): a random self-avoiding walk of length n in the strip [a,b]
#a<=0 b>=0
rasawab:=proc(n,a,b)
local gu,i:
gu:=0:
 
while gu=0 do
gu:=rasawab1(n,a,b):
od:
gu:
end:
 
rasawab1:=proc(n,a,b)
local gu,cu,opts,i,j,kama,opts1,ra:
 
if n<0 then
ERROR(`n>=0`):
fi:
 
if not (type(n,integer) and type(a,integer) and type(b,integer)) then
ERROR(`Inputs must be integers`):
fi:
 
 
if a>0 or b<0 then
ERROR(`a<=0,b>=0`):
fi:
 
gu:=[[0,0]]:
cu:=[0,0]:
 
for j from 1 to n do
opts:={[op(1,cu)+1,op(2,cu)],[op(1,cu)-1,op(2,cu)],
[op(1,cu),op(2,cu)+1],[op(1,cu),op(2,cu)-1]}:
opts:=opts minus convert(gu,set):
 
opts1:=opts:
for i from 1 to nops(opts1) do
 
if op(2,op(i,opts1))=a-1 or op(2,op(i,opts1))=b+1 then
 opts:=opts minus {op(i,opts1)}:
fi:
 
od:
 
kama:=nops(opts):
 
if kama=0 then
RETURN(0):
fi:
 
ra:=rand(1..kama):
 
cu:=op(ra(),opts):
gu:=[op(gu),cu]:
od:
 
gu:
end:
 
 
 
rasaw:=proc(n):rasawab(n,-n-1,n+1):end:
 
Optsab:=proc(Walk,a,b)
local cu,opts,opts1,i:
 
cu:=op(nops(Walk),Walk):
opts:={[op(1,cu)+1,op(2,cu)],[op(1,cu)-1,op(2,cu)],
[op(1,cu),op(2,cu)+1],[op(1,cu),op(2,cu)-1]}:
opts:=opts minus convert(Walk,set):
 
opts1:=opts:
for i from 1 to nops(opts1) do
 
if op(2,op(i,opts1))=a-1 or op(2,op(i,opts1))=b+1 then
 opts:=opts minus {op(i,opts1)}:
fi:
 
od:
 
opts:
end:
 
 
 
Optsabright:=proc(Walk,a,b)
local cu,opts,opts1,i:
 
cu:=op(nops(Walk),Walk):
opts:={[op(1,cu)+1,op(2,cu)],[op(1,cu)-1,op(2,cu)],
[op(1,cu),op(2,cu)+1],[op(1,cu),op(2,cu)-1]}:
opts:=opts minus convert(Walk,set):
 
opts1:=opts:
for i from 1 to nops(opts1) do
 
if op(2,op(i,opts1))=a-1 or op(2,op(i,opts1))=b+1 
or op(1,op(i,opts1))=0 
then
 opts:=opts minus {op(i,opts1)}:
fi:
 
od:
 
opts:
end:
 
 
LWOptsab:=proc(Walk,b)
local cu,opts,opts1,i:
 
cu:=op(nops(Walk),Walk):
opts:={[op(1,cu)+1,op(2,cu)],[op(1,cu),op(2,cu)+1]}:
 
opts1:=opts:
for i from 1 to nops(opts1) do
 
if op(2,op(i,opts1))=b+1 then
 opts:=opts minus {op(i,opts1)}:
fi:
 
od:
 
opts:
end:
 
 
 
Optscom:=proc(Walk)
local cu,opts:
 
cu:=op(nops(Walk),Walk):
opts:={[op(1,cu)+1,op(2,cu)],[op(1,cu)-1,op(2,cu)],
[op(1,cu),op(2,cu)+1],[op(1,cu),op(2,cu)-1]}:
opts:=opts intersect convert(Walk,set):
 
if member([0,0],opts) then
RETURN({[0,0]}):
else
RETURN({}):
fi:
 
end:
 
 
 
Opts:=proc(Walk)
local cu,opts:
 
cu:=op(nops(Walk),Walk):
opts:={[op(1,cu)+1,op(2,cu)],[op(1,cu)-1,op(2,cu)],
[op(1,cu),op(2,cu)+1],[op(1,cu),op(2,cu)-1]}:
opts:=opts minus convert(Walk,set):
 
opts:
end:
 
 
#muav(n,K) find the average number of options a random walk
#of n steps has to make the next step, using a random sample
#of K walks
 
muav:=proc(n,K)
local schum,gu,i,tov:
schum:=0:
tov:=0:
 
for i from 1 to K do
 
gu:=rasaw(n):
 
if gu<>0 then
tov:=tov+1:
schum:=schum+nops(Opts(gu)):
fi:
 
od:
 
evalf(schum/tov):
 
end:
 
 
 
#muavab(n,a,b,K) find the average number of options a random walk
#of n steps has to make the next step, using a random sample
#of K walks
 
muavab:=proc(n,a,b,K)
local schum,gu,i,tov:
schum:=0:
tov:=0:
 
for i from 1 to K do
 
gu:=rasawab(n,a,b):
 
if gu<>0 then
tov:=tov+1:
schum:=schum+nops(Optsab(gu,a,b)):
fi:
 
od:
 
evalf(schum/tov):
 
end:
 
 
#SAW(n): Gives the set of all self-avoiding walks of n steps
#in the 2D square-lattice
 
SAW:=proc(n)
local i,k,ru,mu,gu,wal:
option remember:
 
 
if n<0 or not type(n,integer) then
ERROR(`n>=0`):
fi:
 
if n=0 then
RETURN({[[0,0]]}):
fi:
 
mu:={}:
 
gu:=SAW(n-1):
 
for i from 1 to nops(gu) do
wal:=op(i,gu):
ru:=Opts(wal):
 
 
for k from 1 to nops(ru) do
mu:=mu union {[op(wal),op(k,ru)]}:
od:
 
od:
 
mu:
end:
 
 
#POLYGON(n): Gives the set of all self-avoiding polygons, with the
#origin marked, of n steps
#in the 2D square-lattice
 
POLYGON:=proc(n)
local i,k,ru,mu,gu,wal:
option remember:
 
 
if n<0 or not type(n,integer) then
ERROR(`n>=0`):
fi:
 
if n=0 then
RETURN({}):
fi:
 
mu:={}:
 
gu:=SAW(n-1):
 
for i from 1 to nops(gu) do
wal:=op(i,gu):
ru:=Optscom(wal):
 
 
for k from 1 to nops(ru) do
mu:=mu union {[op(wal),op(k,ru)]}:
od:
 
od:
 
mu:
end:
 
 
 
 
#SAWab(n,a,b): Gives the set of all self-avoiding walks of n steps
#in the 2D square-lattice restricted to the strip [a,b]
 
SAWab:=proc(n,a,b)
local i,k,ru,mu,gu,wal:
option remember:
 
 
if n<0 then
ERROR(`n>=0`):
fi:
 
if not (type(n,integer) and type(a,integer) and type(b,integer)) then
ERROR(`Inputs must be integers`):
fi:
 
 
if a>0 or b<0 then
ERROR(`a<=0,b>=0`):
fi:
 
if n=0 then
RETURN({[[0,0]]}):
fi:
 
mu:={}:
 
gu:=SAWab(n-1,a,b):
 
for i from 1 to nops(gu) do
wal:=op(i,gu):
ru:=Optsab(wal,a,b):
 
 
for k from 1 to nops(ru) do
mu:=mu union {[op(wal),op(k,ru)]}:
od:
 
od:
 
mu:
end:
 
 
 
 
#SAWrightab(n,a,b): Gives the set of all self-avoiding walks of n steps
#in the 2D square-lattice restricted to the strip [a,b], whose first
#visited point (after the origin) is [1,0], and that never
#visit the y-axis except at the origin
 
SAWrightab:=proc(n,a,b)
local i,k,ru,mu,gu,wal:
option remember:
 
 
if n<1 then
ERROR(`n>=1`):
fi:
 
if not (type(n,integer) and type(a,integer) and type(b,integer)) then
ERROR(`Inputs must be integers`):
fi:
 
 
if a>0 or b<0 then
ERROR(`a<=0,b>=0`):
fi:
 
if n=1 then
RETURN({[[0,0],[1,0]]}):
fi:
 
mu:={}:
 
gu:=SAWrightab(n-1,a,b):
 
for i from 1 to nops(gu) do
wal:=op(i,gu):
ru:=Optsabright(wal,a,b):
 
 
for k from 1 to nops(ru) do
mu:=mu union {[op(wal),op(k,ru)]}:
od:
 
od:
 
mu:
end:
 
 
 
 
#LWb(n,b): Gives the set of all lattice walks of n steps
#in the 2D square-lattice restricted to the strip [0,b]
 
LWb:=proc(n,b)
local i,k,ru,mu,gu,wal:
option remember:
 
 
if n<0 then
ERROR(`n>=0`):
fi:
 
if not (type(n,integer)  and type(b,integer)) then
ERROR(`Inputs must be integers`):
fi:
 
 
if  b<0 then
ERROR(` b>=0 `):
fi:
 
if n=0 then
RETURN({[[0,0]]}):
fi:
 
mu:={}:
 
gu:=LWb(n-1,b):
 
for i from 1 to nops(gu) do
wal:=op(i,gu):
ru:=LWOptsab(wal,b):
 
 
for k from 1 to nops(ru) do
mu:=mu union {[op(wal),op(k,ru)]}:
od:
 
od:
 
mu:
end:
 
 
#targem(wal) takes a saw, given in terms of the sequence of points
# and translates it to a sequence of the edges 
 
targem:=proc(wal)
local i,gu:
gu:={}:
 
for i from 1 to nops(wal)-1 do
gu:=gu union {[op(i,wal),op(i+1,wal)]}:
od:
gu:
end:
 
 
 
#findm(wal): given a walk wal finds the smallest x ordinate
#that participates there 
 
findm:=proc(wal)
local edg,katan,i:
 
katan:=0:
 
for i from 1 to nops(wal) do
edg:=op(i,wal):
 
if op(1,op(1,edg))<katan  then
katan:=op(1,op(1,edg)):
fi:
 
if op(1,op(2,edg))<katan  then
katan:=op(1,op(2,edg)):
fi:
 
od:
 
katan:
end:
 
 
#Extractm1(wal,m): Given a saw wal, given in terms of its set of
#directed edges, extracts all those edges of the form [[m,b],[m,b+1]],
#and [[m,b+1],[m]], and [[m,b],[m+1,b]] and [[m+1,b],[m,b]]
 
Extractm1:=proc(wal,m)
local gu,i,edg:
 
gu:={}:
 
for i from 1 to nops(wal) do
edg:=op(i,wal):
 
if op(1,op(1,edg))=m and op(1,op(2,edg))=m then
 gu:=gu union {edg}:
fi:
 
 
 
if op(1,op(1,edg))=m and op(1,op(2,edg))=m+1 then
 gu:=gu union {edg}:
fi:
 
 
 
if op(1,op(1,edg))=m+1 and op(1,op(2,edg))=m then
 gu:=gu union {edg}:
fi:
 
od:
gu:
end:
 
 
#Extractm(wal,m): Given a saw wal, given in terms of its set of
#edges, extracts all those edges of the form [[m,b],[m,b+1]],
#and [[m,b],[m+1,b]] and their revserses and then substracting [m,0]
 
Extractm:=proc(wal,m)
local gu,i,edg,v1,v2:
 
gu:={}:
 
for i from 1 to nops(wal) do
edg:=op(i,wal):
 
v1:=op(1,edg):
v2:=op(2,edg):
 
if op(1,v1)=m and op(1,v2)=m then
 gu:=gu union {[[0,op(2,v1)],[0,op(2,v2)]]}:
fi:
 
 
 
if op(1,v1)=m and op(1,v2)=m+1 then
 gu:=gu union {[[0,op(2,v1)],[1,op(2,v2)]]}:
fi:
 
 
 
if op(1,op(1,edg))=m+1 and op(1,op(2,edg))=m then
 gu:=gu union {[[1,op(2,v1)],[0,op(2,v2)]]}:
fi:
 
od:
 
 
gu:
end:
 
 
 
 
#Extractmg(wal,m): Given a saw wal, given in terms of its set of
#edges, extracts all those edges of the form [[m,b],[m,b+1]],
#and [[m,b],[m+1,b]] and their revserses and then substracting [m,0]
#also has a second component: L or R depending on whether m is negative
#or non-positive
 
Extractmg:=proc(wal,m)
local gu,i,edg,v1,v2:
 
gu:={}:
 
for i from 1 to nops(wal) do
edg:=op(i,wal):
 
v1:=op(1,edg):
v2:=op(2,edg):
 
if op(1,v1)=m and op(1,v2)=m then
 gu:=gu union {[[0,op(2,v1)],[0,op(2,v2)]]}:
fi:
 
 
 
if op(1,v1)=m and op(1,v2)=m+1 then
 gu:=gu union {[[0,op(2,v1)],[1,op(2,v2)]]}:
fi:
 
 
 
if op(1,op(1,edg))=m+1 and op(1,op(2,edg))=m then
 gu:=gu union {[[1,op(2,v1)],[0,op(2,v2)]]}:
fi:
 
od:
 
if gu<>{} then
if m<0 then 
RETURN([gu,L]):
else
RETURN([gu,R]):
fi:
fi:
{}:
end:
 
 
#Targem(wal) takes a saw, given in terms of the sequence of points
# and translates it to a sequence of `letters'
 
Targem:=proc(wal)
local i, mu,lu,gu,kat:
gu:=targem(wal):
kat:=findm(gu):
 
lu:=Extractm(gu,kat):
mu:=[]:
for i from 1 while lu<>{} do
mu:=[op(mu),lu]:
lu:=Extractm(gu,kat+i):
od:
mu:
end:
 
 
 
 
#Targemg(wal) takes a saw, given in terms of the sequence of points
# and translates it to a sequence of `letters' with accounting of
#to the left or right of the origin
 
Targemg:=proc(wal)
local i, mu,lu,gu,kat:
gu:=targem(wal):
kat:=findm(gu):
 
lu:=Extractmg(gu,kat):
mu:=[]:
for i from 1 while lu<>{} do
mu:=[op(mu),lu]:
lu:=Extractmg(gu,kat+i):
od:
mu:
end:
 
 
 
 
SAWW:=proc(n)
local i,gu,mu:
gu:=SAW(n):
 
mu:={}:
 
for i from 1 to nops(gu) do
mu:=mu union {Targem(op(i,gu))}:
od:
mu:
end:
 
 
#SAWWab(OREKH,a,b): the set of all 2D saws in the strip [a,b] 
#whose translation has length<=OREKH
 
SAWWab:=proc(OREKH,a,b)
local i,n,gu,mu,mila:
 
mu:={}:
for n from 0 to (2*(b-a))*OREKH+2 do
gu:=SAWab(n,a,b):
 
for i from 1 to nops(gu) do
mila:=Targem(op(i,gu)):
if nops(mila)<=OREKH then
mu:=mu union {mila}:
fi:
od:
 
od:
 
mu:
end:
 
 
#SAWWabg(OREKH,a,b): the set of all 2D saws in the strip [a,b] 
#whose translation has length<=OREKH where account is taken of
#the things to the left and right of the origin
 
SAWWabg:=proc(OREKH,a,b)
local i,n,gu,mu,mila:
 
mu:={}:
for n from 0 to (2*(b-a))*OREKH+2 do
gu:=SAWab(n,a,b):
 
for i from 1 to nops(gu) do
mila:=Targemg(op(i,gu)):
if nops(mila)<=OREKH then
mu:=mu union {mila}:
fi:
od:
 
od:
 
mu:
end:
 
 
 
 
 
#SAWWrightab(OREKH,a,b): the set of all 2D saws in the strip [a,b] 
#whose first visited point, after the origin is [1,0] and that never
#touch the y-axis, and whose translation has length<=OREKH
 
SAWWrightab:=proc(OREKH,a,b)
local i,n,gu,mu,mila:
 
mu:={}:
for n from 1 to (2*(b-a))*OREKH+3 do
gu:=SAWrightab(n,a,b):
 
for i from 1 to nops(gu) do
mila:=Targem(op(i,gu)):
if nops(mila)<=OREKH then
mu:=mu union {mila}:
fi:
od:
 
od:
 
mu:
end:
 
 
LWWbex:=proc(OREKH,b):
 
if not type(OREKH,integer) or OREKH<1 then
ERROR(`OREKH>=1`):
fi:
 
LWWb(OREKH,b) minus LWWb(OREKH-1,b):
end:
 
 
#LWWb(OREKH,b): the set of all 2D lattice walks in the strip [0,b] 
#whose translation has length<=OREKH
 
LWWb:=proc(OREKH,b)
local i,n,gu,mu,mila:
 
mu:={}:
for n from 0 to OREKH+b+1 do
gu:=LWb(n,b):
 
for i from 1 to nops(gu) do
mila:=Targem(op(i,gu)):
if nops(mila)<=OREKH then
mu:=mu union {mila}:
fi:
od:
od:
 
mu:
end:
 
 
 
#redLWWb(OREKH,b): the set of all 2D lattice walks in the strip [0,b] 
#whose reduced translation has length<=OREKH
 
redLWWb:=proc(OREKH,b)
local i,n,gu,mu,mila:
 
mu:={}:
for n from 0 to OREKH+3 do
gu:=LWb(n,b):
 
for i from 1 to nops(gu) do
mila:=Targem(op(i,gu)):
mila:=reduc(mila)[1]:
if nops(mila)<=OREKH then
mu:=mu union {mila}:
fi:
od:
od:
 
mu:
end:
 
 
#mishkalot(lett): the number of edges participating in a letter
 
mishkalot:=proc(lett)
nops(lett):
end:
 
 
#mishkal(mila): the number of edges participating in a word mila,
#i.e. the sum of the edges of its letters
 
mishkal:=proc(mila)
local i,gu:
gu:=0:
 
for i from 1 to nops(mila) do
gu:=gu+mishkalot(op(i,mila)):
od:
gu:
end:
 
 
#TrySAWr sees whether the language of SAWs in [a,b] is r-Markovian
 
TrySAWr:=proc(a,b,r)
local sa,sa1,di:
sa:=SAWWab(r+2,a,b):
di:=Dikduk(sa,r):
sa1:=Safa(di,r,r+3)[1]:
evalb(sa1 = SAWWab(r+3,a,b) minus SAWWab(r+2,a,b)):
end:
 
 
#TryLWr sees whether the language of LWs in [0,b] is r-Markovian
 
TryLWr:=proc(b,r)
local sa,sa1,sa2,di:
sa:=LWWb(r+2,b):
di:=Dikduk(sa,r):
sa1:=Safa(di,r,r+3)[1]:
sa2:=LWWb(r+3,b) minus LWWb(r+2,b):
evalb(sa1 = sa2):
end:
 
 
 
#gfSawabold(a,b,r,t): Assuming that the sets of SAWs restricted to the
#strip [a,b] is reduced r-Markovian, finds the generating function
 
gfSawabold:=proc(a,b,r,t)
local i,sa,kaful,dik,wt,alfab,ot1:
sa:=SAWWab(r+4,a,b):
sa:=Reduc(sa):
kaful:=sa[2]:
sa:=sa[1]:
dik:=Grammar(sa,r,r+4):
alfab:=dik[6]:
 
for i from 1 to nops(alfab) do
ot1:=op(i,alfab):
if member(ot1,kaful) then
wt[ot1]:=t^nops(ot1)/(1-t^nops(ot1)):
else
wt[ot1]:=t^nops(ot1):
fi:
od:
 
gf(dik,r,wt):
factor(normal(")):
end:
 
 
 
#gfSawab(a,b,r,t): Assuming that the sets of SAWs restricted to the
#strip [a,b] is reduced r-Markovian, finds the generating function
 
gfSawab:=proc(a,b,r,t)
local i,sa,kaful,dik,wt,alfab,ot1,KAMA:
 
for KAMA from 2 do
sa:=SAWWab(r+KAMA,a,b):
sa:=Reduc(sa):
kaful:=sa[2]:
sa:=sa[1]:
dik:=Grammar(sa,r,r+KAMA):
 
if dik<>0 then
alfab:=dik[6]:
 
for i from 1 to nops(alfab) do
ot1:=op(i,alfab):
if member(ot1,kaful) then
wt[ot1]:=t^nops(ot1)/(1-t^nops(ot1)):
else
wt[ot1]:=t^nops(ot1):
fi:
od:
 
gf(dik,r,wt):
RETURN(factor(normal("))):
fi:
od:
end:
 
 
 
 
 
#gfSawabg(a,b,r,t): Assuming that the sets of SAWs restricted to the
#strip [a,b] is reduced r-Markovian, finds the generating function
#(where L and R are being kept track of)
 
gfSawabg:=proc(a,b,r,t)
local i,sa,kaful,dik,wt,alfab,ot1,KAMA:
 
for KAMA from 2 do
sa:=SAWWabg(r+KAMA,a,b):
sa:=Reduc(sa):
kaful:=sa[2]:
sa:=sa[1]:
dik:=Grammar(sa,r,r+KAMA):
 
if dik<>0 then
alfab:=dik[6]:
 
for i from 1 to nops(alfab) do
ot1:=op(i,alfab):
if member(ot1,kaful) then
wt[ot1]:=t^nops(op(1,ot1))/(1-t^nops(op(1,ot1))):
else
wt[ot1]:=t^nops(op(1,ot1)):
fi:
od:
 
gf(dik,r,wt):
RETURN(factor(normal("))):
fi:
od:
end:
 
 
 
#gfSawrightab(a,b,r,t): Assuming that the sets of SAWs restricted to the
#strip [a,b], whose first visited point, after the origin is [1,0] and who  
#never visit the y-axix, except at the origin, is reduced r-Markovian, 
#finds the generating function
 
gfSawrightab:=proc(a,b,r,t)
local i,sa,kaful,dik,wt,alfab,ot1:
sa:=SAWWrightab(r+4,a,b):
sa:=Reduc(sa):
kaful:=sa[2]:
sa:=sa[1]:
dik:=Grammar(sa,r,r+4):
alfab:=dik[6]:
 
for i from 1 to nops(alfab) do
ot1:=op(i,alfab):
if member(ot1,kaful) then
wt[ot1]:=t^nops(ot1)/(1-t^nops(ot1)):
else
wt[ot1]:=t^nops(ot1):
fi:
od:
 
gf(dik,r,wt):
factor(normal(")):
end:
 
 
 
#gfLWWb(b,r,t): Assuming that the sets of LWs restricted to the
#strip [0,b] is reduced r-Markovian, finds the generating function
gfLWWb:=proc(b,r,t)
local i,sa,kaful,dik,wt,alfab,ot1,KAMA:
 
for KAMA from 2 do
sa:=LWWb(r+KAMA,b):
sa:=Reduc(sa):
kaful:=sa[2]:
sa:=sa[1]:
 
dik:=Grammar(sa,r,r+KAMA):
 
if dik<>0 then
alfab:=dik[6]:
 
for i from 1 to nops(alfab) do
ot1:=op(i,alfab):
 
if member(ot1,kaful) then
wt[ot1]:=t^nops(ot1)/(1-t^nops(ot1)):
else
wt[ot1]:=t^nops(ot1):
fi:
od:
 
gf(dik,r,wt):
RETURN(factor(normal("))):
fi:
od:
 
end:
 
savim:=proc(dik1,dik2)
local i:
for i from 1 to 4 do
if dik1[i]<>dik2[i] then
 RETURN(0):
fi:
od:
 
if dik1[6]<>dik2[6] then
 RETURN(0):
fi:
 
 
if op(op(op(dik1[5])))<>op(op(op(dik1[5]))) then
 RETURN(0):
fi:
 
1:
end:
 
 
#RASAWWab(a,b): Generates a random word in the langauage
#of Self-Avoiding Walks in the strip [a,b] after it is translated
#to a sequence of edge-set describing vertical cross-sections with
#a second component describing whether it was to the left or right of
#the origin
 
RASAWWab:=proc(a,b)
local wal,n,rad:
rad:=rand(0..8):
 
n:=(b-a+1)*20+rad();
 
wal:=rasawab(n,a,b):
Targemg(wal):
end:
 
 
RASAWW01g:=proc()
local wal,n,rad,a,b:
a:=0:b:=1:
rad:=rand(0..8):
 
n:=20+rad();
 
wal:=rasawab(n,a,b):
Targemg(wal):
end:
 
 
RASAWW02g:=proc()
local wal,n,rad,a,b:
a:=0:b:=2:
rad:=rand(0..8):
 
n:=60+rad();
 
wal:=rasawab(n,a,b):
Targemg(wal):
end:
 
 
RASAWW03g:=proc()
local wal,n,rad,a,b:
a:=0:b:=3:
rad:=rand(0..8):
 
n:=80+rad();
 
wal:=rasawab(n,a,b):
Targemg(wal):
end:
 
 
 
RASAWW04g:=proc()
local wal,n,rad,a,b:
a:=0:b:=4:
rad:=rand(0..8):
 
n:=100+rad();
 
wal:=rasawab(n,a,b):
Targemg(wal):
end:
 
 
 
 
RASAWW01:=proc()
local wal,n,rad,a,b:
a:=0:b:=1:
rad:=rand(0..8):
 
n:=30+rad();
 
wal:=rasawab(n,a,b):
Targem(wal):
end:
 
 
RASAWW02g:=proc()
local wal,n,rad,a,b:
a:=0:b:=2:
rad:=rand(0..8):
 
n:=40+rad();
 
wal:=rasawab(n,a,b):
Targem(wal):
end:
 
 
RASAWW03:=proc()
local wal,n,rad,a,b:
a:=0:b:=3:
rad:=rand(0..8):
 
n:=60+rad();
 
wal:=rasawab(n,a,b):
Targem(wal):
end:
 
 
 
RASAWW04:=proc()
local wal,n,rad,a,b:
a:=0:b:=4:
rad:=rand(0..8):
 
n:=100+rad();
 
wal:=rasawab(n,a,b):
Targem(wal):
end:
 
 
 
 
#RagfSawab01g(r,t,N,GVUL): Assuming that the sets of SAWs restricted to the
#strip [0,1] is reduced r-Markovian, finds the generating function
#(where L and R are being kept track of) by guessing the grammar by
#picking sufficiently large corpuses drawn from random words
#N is the number of words in the smallest corpus
#GVUL is the limit, to make the program terminate
 
RagfSawab01g:=proc(r,t,N,GVUL)
local sa1,sa2,sa3,di1,di2,di3,gu,saka,di1,di2,di3,dik,a,b:
a:=0:
b:=1:
if not (type(a,integer) and type(b,integer) and a<b and 0<=a) then
ERROR(`Wrong input`):
fi:
 
gu:=CORPUSES(RASAWW01g,N,GVUL):
 
saka:=SAWWabg(r+3,a,b):
 
sa1:=saka union gu[1]:
sa2:=saka union gu[2]:
sa3:=saka union gu[3]:
gu:=Reduc(sa1):
kaful:=gu[2]:
sa1:=gu[1]:
sa2:=Reduc(sa2)[1]:
sa3:=Reduc(sa3)[1]:
 
di1:=Dikduk(sa1,r):
di2:=Dikduk(sa2,r):
di3:=Dikduk(sa3,r):
 
 
if savim(di1,di2)=0 or savim(di2,di3)=0 or di1=0 then
print(`Could not fit a Markovian Grmmar of memory`,r):
print(`Try to either raise r or raise N, the corpus size`):
RETURN(di1,di2,di3):
fi:
 
dik:=di1:
 
alfab:=dik[6]:
 
for i from 1 to nops(alfab) do
ot1:=op(i,alfab):
if member(ot1,kaful) then
wt[ot1]:=t^nops(op(1,ot1))/(1-t^nops(op(1,ot1))):
else
wt[ot1]:=t^nops(op(1,ot1)):
fi:
od:
 
gf(dik,r,wt):
factor(normal(")):
 
end:
 
 
#RagfSawab01(r,t,N,GVUL): Assuming that the sets of SAWs restricted to the
#strip [0,1] is reduced r-Markovian, finds the generating function
# by guessing the grammar by
#picking sufficiently large corpuses drawn from random words
#N is the number of words in the smallest corpus
#GVUL is the limit, to make the program terminate
 
RagfSawab01:=proc(r,t,N,GVUL)
local sa1,sa2,sa3,di1,di2,di3,gu,saka,di1,di2,di3,dik,a,b:
a:=0:
b:=1:
if not (type(a,integer) and type(b,integer) and a<b and 0<=a) then
ERROR(`Wrong input`):
fi:
 
gu:=CORPUSES(RASAWW01,N,GVUL):
 
saka:=SAWWab(r+3,a,b):
 
sa1:=saka union gu[1]:
sa2:=saka union gu[2]:
sa3:=saka union gu[3]:
 
 
 
 
sa1:=Reduc(sa1)[1]:
sa2:=Reduc(sa2)[1]:
gu:=Reduc(sa3):
sa3:=gu[1]:
kaful:=gu[2]:
 
di1:=Dikduk(sa1,r):
di2:=Dikduk(sa2,r):
di3:=Dikduk(sa3,r):
 
if savim(di1,di2)=0 or savim(di2,di3)=0 or di1=0 then
print(`Could not fit a Markovian Grmmar of memory`,r):
print(`Try to either raise r or raise N, the corpus size`):
RETURN(di1,di2,di3):
fi:
 
dik:=di3:
 
alfab:=dik[6]:
 
for i from 1 to nops(alfab) do
ot1:=op(i,alfab):
if member(ot1,kaful) then
wt[ot1]:=t^nops(ot1)/(1-t^nops(ot1)):
else
wt[ot1]:=t^nops(ot1):
fi:
od:
 
gf(dik,r,wt):
factor(normal(")):
 
end: