ѧ
JOURNAL OF SOFTWARE
1999 10 7ڡNo.7 Vol.10 1999



һ׷һо
䡡˹ٹ
ժҪһ׷һԼ󷴺һ걸㷨.ںһ,жһķ,оýΪ׵תķ.оһĹ,Ҳ½ת,Ľոѽ.ѽεĻһַԸ걸һ걸.ͨGȺZʹΪ㡢ֱ.
ؼʡһ,һ,һ㷴һ,һ걸.
ͼšTP18
First-Order Disunification
XU Man-wuPAN Guang-ruiZHOU Rong-guoSONG Xiao-liang LIU Dong-sheng
(Department of Computer Science and TechnologyNanjing UniversityNanjing210093)
(State Key Laboratory for Novel Software TechnologyNanjing UniversityNanjing210093)
AbstractIn this paper, the authors discuss the first-order disunification and the algorithm for computing the complete set of disunifiers. There are many methods for solving unification problem, the method by using translation rules has been thoroughly studied. Many translation rules are also given out in the study of disunification problem. By using translation rules, people usually get some solved forms for the problem. In this paper, the authors are concerted with the method for giving out the complete set of disunifiers based on solved forms. The method becomes more convenient and direct by using functions Gand Z.
Key wordsDisunification, disunifier, most general disunifier, complete set of disunifiers.
һһҪļ,㷺Ӧڼѧĸ֧.оؿ,һҲ𽥷ḻ.бȽϵ͵зʽһE-unification߽׺һhigh-order unificationԼһsemi-unification.ܵ˵,оЩһʱ,Ҫĵǡȡȡ.,оʽԵģʽƥʱ,ҪһЩӷѧϰ⣻одϵͳʱ,Ҫйس걸Ե,ȵ,Щǣ浽ˡȡ.ְһĿɡȡתˡȡ,͵ˡһ⡱о.
˵,ںһ⡴s=t,ǹĵһӦ,ʹæs=tڷһ⡴st,ǹĵЩʹʽ滻,ʹæs٦t.
ڶԷһоĹ,ǲɱҪպͽһеһЩ.ںһ,жһķ,бȽϵ͵ת1.оһĹ,Ҳ½ת2,Ľոѽ.ڱ,ǹĵѽεĻһַ,Ը걸һ걸.ͨGȺZ,ʹΪ㡢ֱ.չǰ,һЩԼ.
ڱ漰һ,һеĵȼ۹ϵָȼ۹ϵ,١ָ治ȼ۹ϵ.
Varʾɡбɵļ,С,滻,ҲGȺZ(s,t)ж壩.
ԡʾ滻ĸ.,ҺͦȵĸΪҡ,tT,ҡ(t)=((t)).
йصĸοף1,3,4.
1 
1.1. һ,һ.
θԡs,t,Ƿ滻,ʹæs٦t,Ҷ滻.Ƿһ,Ϊst.Ħ,ҳΪһ.
1.2. һ㷴һ,һ㷴һӵļ,һӵ걸,һ㷴һӵ걸.
(1) ķһ⡴st,зһӹɵļϼΪDU(s,t),ڲ¼ΪDU.
(2) MGDU(s,t)ΪMGDUʾstһ㷴һӣ
ҡDU,MGDUҽȡDU,ȡܦ,=ȣ˴,ȡܦ,ָڦʹæѡ=ң.
(3) cDUΪstķһ걸,㣺
(3.1) cDUDU
(3.2) ȡDU,ڦҡcDUʹҡܦ.
(4) DUʾһ㷴һӵļϣһ㷴һӹɵļ.
(5) cDUһ㷴һӵ걸cDUǦDUļ.
2 ض
Ϊ˱,ڴһЩҪ׼.
,滻ĹϵԼ滻ʱ,ֱʹ滻۲תΪʽΪ,ǽһĳ滻ȶӦĺG,GȡڡT.֪,TǶںFͿV֮ϵ.˵GȡڡT,˼GF.
G¹ϵs,tT,
Var(s)Var(t)={x1,x2,...,xn}.
Ϊ滻(Id)ʱ,ȶӦGId(x1,x2,...,xn).
{t1/y1,...,tm/ym}ʱ,ȶӦ
G=GId=GId((x1),(x2),...,(xn))=G(s1,s2,...,sn),
si=(xi).
Ϊ˷㣬ɽG(s1,s2,...,sn)ΪG.
ЦȼӦG(s1,s2,...,sn),ȡ=ʱ,ҶӦ
G=Gȡ=G=G((s1),(s2),...,(sn))=G(r1,r2,...,rn),
ri=(si).
,G(s1,s2,...,sn)=G(r1,r2,...,rm)ҽm=nrisi.
,Ȼ滻Ĺϵ,ǹĵǵͬ滻ԡs,tʱЧкβͬ,ʴ,ǰs,tΪһԴ,һs,tйصġTĶԪZ(s,t),ZĿλ÷ֱst,Ҷ滻
(Z(s,t))=Z((s),(t)).
,Z(s1,t1)=Z(s2,t2)ҽs1=s2t1=t2.һ,滻ԡs,tþͱ˶Z(s,t),Ϊ.Ҫע,G,Z,ǶT,,G,ZTЩ滻.
,ǵ׼.ضо.
2.1. ԡs,t,Ϊs,tĺһ,Ϊs,tķһ,

֤:÷֤.ڦ1,2,ʹ
(1)
ʽ(1)

ڦΪs,tĺһ,

ʽ(2(3

ʽ(4Ϊs,tķһì.֤.
2.2. ԡs,t,Ϊs,tһһӣMGU,Ϊs,tķһ,ҽ12(
֤:֤,ɶ2.1Եõ.֤,÷֤.
ҲΪs,tķһ,شڦ,ʹ,Ǻһ.ڦΪMGU,Դڦ,ʹ


ì,ʦΪs,tķһ.
Ҫע,2.2ЦȱΪMGU,Ҫȶ2.1ϸһЩ,,2.2.,ԡs,t,s=x,t=y,Сs,tһһӦ={g(a)/x,g(a)/y}Լ滻={h(a)/x,h(a)/y},,ȴǷһ,Ǻһ.
2.3. ֪ԡs,tϵ滻Ⱥͦ,滻1,2,
ҽ1Gȡ٦2G.
֤:֤.

֪ɵãشĳxiVar(s)Var(t),
1(xi)٦2(xi).(5)
ʽ(5)ɵGId(1(x1),...,1(xi),...,1(xn))GId(2(x1),...,2(xi),...,2(xn)),
G1G2,
Gȡ1Gҡ2,
1Gȡ٦2G.
֤.
֪1Gȡ٦2Gҿɵ

2.4. ֪ԡs,tϵ滻Ⱥͦ,
ҽ12(1Gȡ٦2G).
֤:֤,÷֤.ڦ1,2,ʹæ1G=2G,

ʽ(6)ãθxiVar(s)Var(t),
ȡ1(xi)=ҡ2(xi).(7)
ʽ(7)ɵ
(8)

 (9)
ʽ(8)(9)

ì.
֤,÷֤.
ڦ1,2,ʹ,θxiVar(s)Var(t),
(10)
ʽ(10)á
1G=2G,
12(1Gȡ٦2G)ì.
,.
2.5. ֪ԡs,tϵ滻Ⱥͦ,Var(G)Var(G)=,(Gȡ٦G)ҽ12(1Gȡ٦2G).
֤֤,÷֤.
ڦ1,2,ʹæ1G=2G,Ц1{t1/x1,...,tn/xn},2{r1/y1,...,rm/ym},æ1,2滻

=ӡ1Ȧӡ2.
ڦ1{ti/xixiVar(G)}GȲãͬ,2{ri/ yiyiVar(G)}GҲ,
1G=ӡ1G,2G=ӡ2G.(11)
Var(G)Var(G)=,,θti/xiʦӡ1,xiVar(G).ͬ,θri/yiʦӡ2,yiVar(G),,
G=ӡ1G,G=ӡ2Gҡ(12)
ʽ(11)(12)
G=ӡ1G=1G,G=ӡ2G=2G.(13)
ʽ(13)ͷ֤
G=G,
(Gȡ٦G)ì.
֤,÷֤.ڦʹæG=G,Ц{t1/x1,...,tn/xn}.ǹ滻

{ti/xixiVar(G)}滻жGȲ,
G=1G.(14)
ͬ
G=2G.(15)
ʽ(14)(15)ɵ
1G=2G,
12(1Gȡ٦2G)ì.
,.
2.6. ֪ԡs,tһһӦ,ٺ1Ԫڵ1ĺ.r/xʦ,rTrквͬxı˵y,s,tһ㷴һ.
֤֪fF,arity(f)=k(k1),
r/xʦ,yVar(r).
ǹһϵ滻

֤,iǷһ,i֮䣨ij(ij)֮䣩ڦiܦjjܦiĹϵ.i֮x滻ģʽͬ,Թͬһ㷴һ,˴׸.ڦiĹ̿޵ȥ,ʡs,tһ㷴һ.
2.7. ֪ԡs,t,FвԪ,ٺ1Ԫڵ1ĺ.s,tΨһһ㷴һӦ,ұΪ滻.
֤:ҲΪ滻,s,tشһһӦȣΪs,tһһӵҽһ㷴һΪ滻.FвԪ,ʴr/xʦ,rквͬxıy,yVar(s)ȪVar(t).ɶ1.6֪,s,tһ㷴һ,֪еġs,tΨһһ㷴һӦì.ʦֻǺ滻.
ע,FвܺԪ,.,֪s,t,s=x,t=a,F={f,a},arity(f)=1,arity(a)=0,ͨ۲֪x,aһ㷴һΨһ,Ϊ={f(x)/x},Ǻ滻={x/x}.
3 һ
ǽǰĽ󷴺һӵ걸.2.2֪һӦһһӦȵĹϵ,

Цǿ,ҪǦ.Ǧ1,2,ʽ߶ȷ,ȥҲ֤ܦ1,2 䶯ʽʼճ?
ǰȶӦĺG,ɶ2.3Ͷ2.4,ǿ԰ѦҵĹϵתGGҵĹϵ.һ,ϣͨG,ʹæ12(1Gȡ٦2G),Ҳʹæ2(Z(s,t))),ӶõGҶӦĦ,ҾǷһ.
ͨһССתѦ1ͦ2䶯Ĳ.
һºһӾͿԿ,һһӦ൱һģʽ,ĺһֻĳִ.ҵһЩȫͬһһӦģʽ滻,Щ滻Ϊһ,ҲǶ2.12.2ĺ.
ȻһһӦһģʽ,ǾͰӦGебдһЩȫͬTķϵͳSķ.磬Sкб,ǿ԰G(f(x),y)дGȡ(f(),ڹ滻ӦGʱTķϵͳ.һVar(Gȡ)Var(G)=.
ֻҪʹGGȡ䲻ܺһһڷϵͳTS½еģ,ڶ2.5ɵæ12(1Gȡ٦2G).,1ͦ2䶯ͽ.,Gֻҵеķ,GIdλôп,Gȡкһ,Gȡ䲻ɺһG,жӦĦҾ͹ɷһӵ걸.
4 
һһΪ۷һ,Ը߽ͷʽһΪַ̽һ൱ӵ,й,ǽԺĹнһȥ̽.
оõȻѧ͹863߿ƼĿ.,1944,ʿ,,ҪоΪ,㷨.˹,1972,˶ʿ,ҪоΪ,㷨.ٹ,1976,˶ʿ,ҪоΪ,㷨.,1974,˶ʿ,ҪоΪ,㷨.,1971,˶ʿ,ҪоΪ,㷨.
ͨѶϵ:,Ͼ210093,Ͼѧѧ뼼ϵ
ߵλϾѧѧ뼼ϵϾ210093Ͼѧ¼صʵҡϾ210093
E-mail: mwxu@netra.nju.edu.cn
ο
1Gallier Jean H, Snyder Wayne. Complete sets of transformations for general E-unification. Theorem Computer Science, 1989,67:203260
2Comon Hubert, Lescanne Pierre. Equational problems and disunification. Journal of Symbolic Computation,1989,7(3&4):371425
3Siekmann Jrgh. Unification theory. Journal of Symbolic Computation. 1989,7(3&4):207274
4Mitchell John C. Foundations for programming languages. Cambridge, MA: MIT Press, 1996
1998-04-07յԭ 
1998-08-03յ޸ĸ
