ѧ
JOURNAL OF SOFTWARE
1999ꡡ1011ڡVol.10No.111999



Ƕνʵʽϵģ
ֻ
ժҪֵǨͼһ㴫̵ֵģ,ǿģȼۿԹΪνʵʽϵ.Ľһƹ㵽ģȼ,Ϊ,Ƕνʵʽϵĸ,㷨,ֵǨͼģȼ۹ΪE2E1Ƕνʵʽϵ.
ؼʡֵ,ģ,νʵʽϵ.
ͼšTP301
Nesting Predicate Equation Systems and Weak Bisimulations
LIN Hui-min
(Laboratory of Computer Science Institute of Software The Chinese Academy of Sciences Beijing 100080)
Abstract Symbolic transition graphs with assignment is a general semantical model for value-passing processes. Strong bisimulation equivalences between such graphs can be reduced to the greatest solutions to simple predicate equation systems. The aim of this paper is to generalise this result to weak bisimulation equivalences. For this purpose, the notion of nesting predicate equation systems is introduced, and algorithms are presented to reduce weak bisimulation equivalences to the greatest solutions to nesting predicate equation systems of the form E2E1.
Key wordsValue-passing processes, bisimulation, predicate equation systems
ף1,2˴ֵķǨͼsymbolic transition graphs with assignment,STGAΪһ㴫̵ֵļģ.STGAڷǨͼ3ݵĻ˸ֵ㣬Աʾڲ״̬ĸı䣬ܴһഫ̶ֵԱʾΪ״̬STGA.CCSΪһ򣨼ݹ鶨вֲиϣCCS̶ֵӦһ״̬STGA.״̬STGAһŵ,ڲи·գ״̬STGAиϵĽȻ״̬STGA2ݣ,STGAԱʾ(networks of parallel processes).ֵǨͼǿģȼۿһ׹ʽ̻ͼǿģ⵱ҽӦĹʽΪ3.ԴֵķǨͼ,һһ㲻ٳ,ף3νʵʽϵĸһνӼ벻㣬㷨,STGAǿģΪνʵʽϵ.
ǿģȼҪϵ壬ʵʹõĵȼ۹ϵǽʾڲͨŵĲɼӳõģȼۣ4.ĵĿǽף1ݵĽƹ㵽ģȼ.ڼ򵥵νʵʽϵԿ̻ģ,Ϊ,Ƕνʵʽϵĸ֤伫󡢼СĴԣȻνSTGAģȼ۹ΪΪ2Ƕνʵʽϵ.
Ϊʡƪ,ף1ݵ2͵3еĻǺż,Ĳظ.
1 Ƕνʵʽϵ
ٶݱDV={x,y,z,...}ݱϵݱʽDExpͲʽBExpνʱPV={X,Y,Z,...}ף1ݵ3ڶʽ⦵νʦ.עνʵĹûʹ÷񶨴ʣνʱ̺ʽ󲿳.ֵValT={true,false}.ݱĸֵѽݱӳΪValеԪ.ѿ쵽DExpBExp:һeDExp,(e)ValһbBExp,(b)T.νʱĸֵνʱӳΪռValnTеԪ(nΪνʱ).Ѻͣɶ幫ʽνʦ壬ף1еĵ3.falsetrue䵽ռValTϣһ䵽νʱĸֵף1еĵ3.֤,ȫνʱԪֵ¹걸.{Xi|iI}νʱ޼E{Xi=i|iI}ΪһνʵʽϵiXiͬͣҶijXiXj.ʽ{Xi=i|iI}ɼдΪ=.k{1,...,n}k{,}k٦k-1(k>1)Ek:k=kνʵʽϵҶkj{k}{j}=

ǽΪnǶνʵʽϵ.ΪдkʾEkk-1Ek-1...1E1.ѺͣnĽƹɶ:

,ʾڦѺ͵(ҡ)С(ҡ)nĽҲǷĲ.ĺⱣ֤.
1.1. ѺͣǶνʵʽϵС.
֤:ȫνʱĸֵ¹걸걸ϵĵС5ݣֻ֤򵥵Ǽٶơơ壬֤nʩ.
(ʼ) n=1.ʱʽϵǶףǦơͦǦơ嶼ǿս⣬,{Ǧ}{ơ}={ơ},{Ǧơ}{ơ}={ơ}.ɦơơ֪,{ơ}{ơ}ڡ1νʱ̺ʽ󲿣,.
(ɲ) ۶ǶΪn-1ĵʽϵn=Enn-1n-1n-1Ԧ̣ɹɼ˦ƹڵ,n-1йڦ,{ơ}С͹ڦѣ{ơ}С㣬Ӧơơ֪,{ơ}{ơ},ǦơǦơ},{Ǧơ}{ơ}{Ǧơ}{ơ}ڡnνʱ̺ʽ󲿳֣.
Ԥ1.1. νʵʽϵiеνʱԪEڦѺ͵С.(Yi0)(i0)=true,i0I,ҽi1,...,ik,k0(i1,...,ikػͬ)ilJil-1,

Ц0=,l+1=l{ il|il},il=l(il).
֤ɦ(Yi0)(i0)=true֪,

,Ԥѵ֤(ڦiеνʱԪ.,i1Ji0ʹ.
1(bi1)Ħ(Yi1)(i1)=true.
Ԧ(Yi1)(i1)=trueɼͬ.Сʣĳkʹáikk,V=trueҶ1lkЦl(bil)Ħ(Yil)(il)=true.
2 STGAģ⼰߼̻
ڴֵǨͼϸοף1ݵ2.
2.1ֵǨͼSTGAһͼÿnɱfv(n)ÿ߱ɲʽֵͶɵԪ飬㣺nmǴnmһߣfv(b,)fv(n),fv(){},fv(m){}bv().
,bǲʽ,eݱʽ{,c?x,c!e|cͨ}c?xΪ붯c!eΪǱʾڲͨŵĲɼ.һֵķǨͼ,ϵ״̬ռǵĽ㣬ѡEVal}.STGAĳٲ״̬ϵǨƹϵй.

Ϊ˶ģ⣬˫ͷǨ.ҽa{ӡ,c!}ҽ,.
2.2. ״̬ϵĶԳƶԪϵRǳģ⣬{m,ne}R̺,
.ֻҪУҶԡValneۦ/yne,(mѣۦ/x,ne)R.
.aֻҪmmѡ䣬nene䣬(mѡ,ne)R.={R|Rһģ.}
̻ģҪΪ2ǶνʵʽϵE2E1ֱ۵˵,ʽϵE2̻ģ⣬ڲʽϵE1զӶ.
ֿռ䲻ཻSTGA,Ľm,m,mi,...ʾ;Ľn,n,nj,...ʾ;m,m,mi,...ıΪ,,i,...;n,n,nj,...ıΪ,,j, ....㷨1е㷨E2E1ĵʽϵ.㷨üVisited,Visited,m,n,Visited,c!e,m,n,Visitedc?x,m,n֤ÿһӦĻ·ֻһ.Щɹinit()Ϊռ.,ƥ붯ʱʹúnewVar()һµݱ.emitνʵʽ.idʾ滻.
㷨νʵʽ4ֱ࣬
Xm,n(,)=Vclose
closeӲ
matchc!
matchc?
E2Ϊɵ1ʽɵĵʽϵ,E1Ϊ3ʽɵĵʽϵ.E2E1Ϊ㷨Ƕνʵʽϵ.ѿ,E2E1ǱյģE1ĸʽУұߵĵ1ȡвE1󲿳ֵνʱԪ.
㷨1. ģ㷨
bisim(m,,n,)=init()
close(m,,n,)
close(m,,n,)=
ifm,nVisited then{
Visited={m,n}Visited
emit(Xm,n=Vmatch(m,n))}
return Xm,n(,)
match(m,n)=match(m,n)match\-(n,m)
match(m,n)=bimatch(i,mi,n)
closeT(m,,n,)=
B=close(m,,n,)
for each nnl
ifm,nlVisited,m,n then{
Visited,m,n={m,nl}Visited,m,n
emit(Ym,nl=close(m,,nl,id))}
return(BblYm,nl(id,l))
match(m,n)=close(m,,n,id)
matchc!(m,n)=bimatchc!(i,mi,n)
matchc!(,m,n)=
for each nnj
Bj=close(m,,nj,j)
for each nnl
if m,nlVisited,c!e,m,n then{
Visited,c!e,m,n={m,nl}Visited,c!e,m,n
emit(Y,c!e,m,nl=matchc!(,c!e,m,nl)}
return(bje=ejjBj)(blY,c!e,m,nl(id,ҡl))
matchc?(m,n)=bimatchc?(i,x,mi,n)
matchc?(,x,m,n)=
for each nnj
z=new Var()
Bj=close(m,ȣx|z,nj,jy|z)
Bj=Bj
for each nnl
if m,nlVisitedc?x,m,n then{
Visitedc!x,m,n={m,nl}Visited,c?x,m,n
emit(Yc?x,m,nl=matchc?(,x,m,nl)}
return((bjBj)(blYc?x,m,nl(id,ҡl)))
Ԥ2.1.  E1ڦƵС⣬YM,n(,)/,/,{}=trueMm,c!e,mc?x,m,0=/yݣn,,E1еʽ
YM,n(,)=(blYM,nl(,l)),
ʹn0/1n/,ҡ/,/,{}=true.
֤MmΪ.Ԥ1.1lj,0j<k,k0,nl0=nE1еʽ

ljjlj-1,j1,
bljlj/lj=true,
(Ym,nlj)(,lj)=true,
lk/,lk/lk,{}=true,
l0=,lj=ljlj-1/lj-1.ɺclose֪,

,nl0/,/nl1/,l1/l1...nlk/,lk/lk.n=nlk,=lk,=lk,=lk֤.
2.1. E2E1㷨1ǶνʵʽϵE2E1Ľ.(Xm,n)(,)=trueҽm/ݡn/,,ֱmnɱ.
֤()S={(m/,n/)|(Xm,n)(,)=true}֤Sģ.(m/,n/)S,(Xm,n)(,)=m,n/,/,{}=true,,E1ڣ/,/ݺͦƵС.ֱǴm/ݳ3Ǩ.
(1),бbi/=true,(eii)/=v,mi=m.m,nһȡbii.bi/=trueái/,/,{}=true.i(bjeii=ejjBj)(blYi,c!ei,mi,nl(,l)).
(1.1) j,bjeij=ejjBj/,/,{}=true,бnnj=[j:=j],bj/=true,(ejj)/=(eii)/=v.Ӷn/njj/j,j=j/,ͬʱ,Bj/,/,{}=true.BjXmj,nj(i,j)(blYmi,nl(,l)).Ǧi=i:=i,i=/
