ѧ
Journal of Software
2000 Vol.11 No.1 P.91-94



ģʽµķһ㷨
˷ʩ
ժҪ֤˶ģʽ´Сһ,һַһ㷨,˶ģʽ·һӦ.
ؼʡһ,һ,ģʽ,㷨,.
ͼšTP301
Anti-Unification Algorithm Based on Multi-Pattern
XU Xi-chunHU Yun-faSHI Bai-le
(Department of Computer ScienceFudan UniversityShanghai200433)
XU Xi-chun
(Computing CenterShanghai Maritime UniversityShanghai200135)
AbstractIn this paper, the existence of the least anti-unification in multi-pattern is proved and an algorithm for the anti-unification is proposed. In addition, the application of the anti-unification in multi-pattern is also introduced.
Key wordsUnification, anti-unification, multi-pattern, algorithm, similarity.
һ½,һӦķһСϽ.һڶ֤ԶȷҪ,һͬҲһַǳõĲ,Ӧдѧϰȷ.Щ,Էһоڼǿ.һPlotkin1ݺReynolds2ݷֱ.һһ,һҲڸʽ.,ѧ߶Ըʽķһо.Page3о˻ڸԼʽķһ,ԼķһԱֳ(overgeneralization).Hasker4о˶׷һ,׷һ԰Ϣ,ڶСһ,֤ͨõȷķһ.Pfenning5о˻͵ġԦΪķһ,ҲһԼ,ͬԱֳ.Щоһͬص㣺߼ṹڵģʽ,νP,ģʽP(a1,a2,...)Ψһ.ǣڲͬӦпжģʽ,,ϵͳأ,ʱһжʽ.Ȼ,Ҳòͬνʾ,,һ,乲Բܱʾһ,ʹνĿɱ.
ĶԶģʽµķһо,֤ڶģʽ´Сһ,˼Сһ㷨.
1
ǰбļϼΪV,ļϼΪC,͵ļϼΪT.ڴ˻,Ƕйظ.
1. ģʽ.νPģʽΪPx1:t1,x2:t2,...,xn:tn),xiΪ,tiΪ.
ǲñʽ͵˼,ÿһνҲ,νPҲΪP,ģʽҲԱʾΪP(t1(x1),t2(x2),...,tn(xn)),,ģʽеĲҲһģʽ,ڹϵݿеķǵһʽ.ǿ԰ѣһֲ.
2. ģʽ.νPڶģʽ,ʾʽ
P(t1(x1),t2(x2),...,tn(xn));
P(t1(x1),t2(x2),...,ti(xi),...,tn(xn)),
У ݱʾѡ.
3. ģʽ.PģʽΪP(t1(x1),t2(x2),...,ti(xi),...,tn(xn)),P(t1(x1),t2(x2),...,ti(xi),...,tn(xn))P(t1(x1),t2(x2),...,ti-1(xi-1),ti+1(xi+1),...,tn(xn))ģʽP(t1(x1),t2(x2),...,ti(xi),...,tn(xn))ĵģʽ.
4. ģʽ.ģʽP1(x1,x2,...,xn),P2(y1,y2,...,ym),P1,P2ͬ,κi(1,n),j(1,m),xi=yi,Ҷi1<i2,j1<j2.
5. ģʽĺϲ.ģʽP1(x1,x2,...,xn),P2(y1,y2,...,ym)ΪPĵģʽ,P1,P2ĺϲģʽP0(z1,z2,...,zn)ΪPĵģʽаģʽP1,P2Сģʽ.
1. ģʽĺϲΨһ.
6. ʵ.ģʽPи,ͬ͵,ΪPʵ.ʾ,ֻܴѡĲ.
7. .¼ʽ(1)Ϊ(2) Ϊ(3) Ϊ(4) ģʽPʵΪ. 
2һ
һʵСϽ.Ϊ˱ȽϴС,ںһ,滻һʵ.
8. ʵ.t,s,滻,ʹæt=s,ʵΪts,Ϊts.
һ滻,õͬʵ.֮෴,Ҳñ,õͬĳ,Ƿһ.
9. һ.t,s,滻,ȼg,ʹæg=t,g=s,gΪt,sķһ.
һһĹͬʵ(ʵ),ͬ,һһСһ.
10. Сһ.gΪt,sķһ,κt,sķһq,gq,gΪt,sСһ.
11. ģʽµķһ.νPģʽʵt,s,滻,ȼPģʽʵg,ʹæg=t,g=s,gΪt,sڶģʽµķһ.
PҲһ,gΪP(x),xΪ.滻¼ʽ(1) x,(2) xQ(...),(3) x(t1,t2,...,tn).
һ,ҪP(t1,t2,...,tn)ΪPʵ.
ף1,4ݵо,ڵģʽ,Ľ.
2. Сһ׷һ.
3. СĶ׷һ.
ڶģʽ,ǿԵó4.
4. ģʽ´Сһ.
֤ģʽPʵA,B,3
(1) A,BΪPͬһģʽʵ.
(2) A,BֱΪPģʽʵ.
(3) A,BΪPģʽʵ((1),(2)֮)
Ƿֱ3֤.
(1),ݶ2,Сһ.
(2),PģʽΪP1,P2.ȿԵõP1,P2ĲP0,ݶ1,P0Ψһ.Ȼ,A,BӳΪP0ʵA0,B0.ݶ2,ֻҪ֤AA0ӳΨһļ.P0P1,P2ĺϲ,,P0P1,P0i,P1,A0iAi䲻P1,ȡA0i.Ȼ,A0iΨһ.
(3),A,BʽΪP(a1,a2,...,an),P(b1,b2,...,bm),nmԲͬ.ݶ11,P(x)A,Bķһ.ֻҪ֤P(x)ΪСһ.
P(x)Сһ,ضһһP(y1,y2,...,yk),kһ1.A,BΪͬģʽʵ,A,Bбشi,ʹai,biͲһ,滻,yiyiai,yibi,ֻyi,yibiyiai,yi.ʣಿƥ(һ),BģʽذAģʽ,.ʣಿֻǲƥ,ôͬ,ڷһP(y1,y2,...,yk),AģʽBģʽΪһģʽĵģʽ.˲ΪP(y1,y2,...,yk)ķһ,P(x)ΪСһ.

3һ㷨
ϽڵĽ,ڶģʽ,Сһ,㷨.
㷨1. һ㷨AU
룺νPģʽPģʽʵ1,2
1,2Сһ
(1) 1,2ΪνPͬһģʽʵ
AU(1,2)P(...AU(xi,yi)...)
(2) 1,2ΪνPһģʽĲͬģʽP1,P2ʵ
P1,P2ĺϲģʽP0
Ѧ1,2תΪP0ʵ11,12
AU(1,2)AU(11,12)P(...AU(x1i,y1i)...)
(3) 1,2ΪνPĲͬģʽP1,P2ʵ
AU(1,2)P(x),
xΪһ±.
5. 㷨AUȷ.
֤ԴӶ4ֱ֤ӵ.
4Ӧ
ģʽµķһӦ෽.öģʽµķһӢľӵ.
t,sķһg,Ҳt,sĸ(),gt,sԽӽ,˵t,sԽ,tsԿ滻,̻

ǲף6ݽܵ䷨еṹʾӢľ,ģʽ.,SһģʽΪ

1You and John are happy롰I studied English yesterdayӿɱʾΪ

һĽΪ

ƶΪ

2They wrote letters yesterday롰I studied English yesterdayӿԱʾΪ

һĽΪ

ƶ

ֱϿ,1ȫƵ,2ǺƵ,ǵֱһµ.
5ᡡ
һһһ,һַǳõĲ.Զģʽ,Էһо,֤ڶģʽ´Сһ,Сһ㷨.Ļöģʽµķһ㷨ΪԼķ,һӦĿǰʵֽ׶εĻڰӢϵͳ.
ѧѧϵϺ200433ϺѧԺġϺ200135
˷ѧѧϵϺ200433)
ʩ֣ѧѧϵϺ200433)
E-mail: xcxu@shmtu.edu.cn
ο
1Plotkin G D. A note on inductive generalization. In: Meltzer B, Michie D eds. Machine Intelligence 5. Edinburgh: Edinburgh University Press, 1970. 153163
2Reynolds J C. Transformational systems and the algebraic structure of atomic formulas. In: Meltzer B, Michie D eds. Machine Intelligence 5. Edinburgh: Edinburgh University Press, 1970. 135151
3Page C D. Anti-Unification in constraint logics: foundations and applications to learn ability in first-order logic, to speed-up learning, and to deduction Ph.D. Thesis. Urbana-Champaign, Illinois: University of Illinois at Urbana-Champaign,1993
4Hasker R W. The replay of program derivations Ph.D. Thesis. Urbana-Champaign, Illinois: University of Illinois at Urbana-Champaign, 1995
5Pfenning F. Unification and anti-unification in the calculus of constructions. In: Kahu G ed. Proceedings of the 6th Annual IEEE Symposium on Logic in Computer Science. Los Alamitos, CA: IEEE Computer Society Press, 1991. 7485
6Lin Tian-ming, Li Gui-wan. Generative grammar of English. Guangzhou: Guangdong People's Press, 1983
(.Ӣ䷨.ݣ㶫磬1983)
1998-09-25ո
1999-02-01޸
