A Unification Algorithm for Infinite Trees
Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Logic Programming. Pages 547-548.
© 1983 International Joint Conferences on Artificial Intelligence
Abstract
A simple unification algorithm for infinite trees has been developed. The algorithm i s designed to work efficiently under structure sh a ring implementa tions of logic programming languages, e.g., Prolog (Warren [3)). A relation, called "is covered with", betw ee n two terms is introduced to terminate the a lgorithm. The fund a mental operations are to comp ute the frontier set of two given terms and to test the relation between them. A termination proof is shown.
- Martelli, A., and Montanari, U. An Efficient Unification Algorithm. ACM Trans. on Program- ming Lang. and Syst., Vol.4, No.2, April 1982.
- Colmerauer, A. Prolog and Infinite Trees . Logic Programming, Academic Press, 1982.
- Warren, D.H . D: Implementing Prolog -Compil- ing Predicate Logic Programs, Dept. of AI , Univ. of Edinb urgh Research Report 39&40 , 1977.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
ABSTRACT
A simple unification algorithm for infinite trees has been developed. The algorithm i s designed to work efficiently under structure sharing imple mentations of logic programming languages, e.g., Prolog (Warren [3)). A relation, called "is covered with", between two terms is introduced to terminate the algorithm. The fundamental operations are to compute the frontier set of two given terms and to test the relation between them. A termination proof is shown.
I INTRODUCTION
The objective of this paper is to explain a practical unification algorithm for infinite trees. In Colmeraue r [ 2], he presents implicitly two algo rithms, a "theoretical" and a "practical" one. For any given two terms, the theoretical algorithm has to select the smaller one in view of length. Although the practical one avoids the test, it is not known to have guaranteed termination. We found a relation which is called "is covered with" and is able to play the same role as the "smaller" rela tion above. It depends on only the frontier (Martelli [1]) of the two term given. This is a main different point from Colmerauer [2].
To describe our uni f ication model, we will use a set of multi-equations to represent variable binding information. A configuration of the uni fica tion process is represented by an ordered pair of a list of equations and a set of multi-equations. We view unification processes as transformations between two configurations.
Now, we will briefly explain a key point of the a lgorithm. Let's imagine the following situa tion : a current value of a variable v is a term b, and v=t is the current equation, where t is a non variable term. With this situation, we first test whether b "is covered with" t. If this is not the case , we change it so that the new value of v will be t. All other points of the algorithm are usual.
II BASIC DEFINITIONS
Definition. A configuration of unification is an ordered pair of the form (R, M), where R is a list of equations of the form term=term, and M is a
A UNIFICATION ALGORITHM FOR INFINITE TREES
Kuniaki Mukai
Institute for New Genera tion Computer Technology Mita Kokusai Bldg. 21F 4-28 Mita 1-chome Minato-ku Tokyo 108 Japan
se t of multi-equations .
Example . The configuration
( <x=y ,y=x> , { {x}=f(x) , {y}=f(y), {z}=f(z) }) rep resents the si tuation :
- The current values of variab l es x , y and z are f(x), f(y) and f(z) , and
- r emaining pairs of terms to be unified a r e {x , y} and {y , z}.
Definition. SUBTERH( t)is the se t of all sub t erms oft , and SUBTERM'(t) is the se t of all proper sub terms of t. Fo r the special t e rm "undef", we use the f ollowing definitions:
SUBTERM( "unde f " ) = { "unde f " }, SUBTERM' ( "undef ") ={} (empty set).
Example.
SUBTERM(f(g(x) ,l)) ={f(g (x) ,1) , g(x) ,x,l} SUBTERM'(f (g(x),l))={ g(x),x,l } .
For convenience , we will extend the definitions SUB TERM and SUBTERMS ' fo r lists of equations , list s of multi-equations, and configurations. Le t Rand H be a list of equations and a set of multi- equa tions .
Definition. SUBTERM(R) is the set of all subterms of the nonvariable left or right hand s ide of some equation in R. SUBTERM'(R) i s the set of all pro per subterms of the nonvariab le l ef t or right hand side of some equation in R. SUBTERM(M) is the set of all subterms of the right hand side of some multi-equation in M. SUBTERN' (M) is the set of all the proper subterms of the right hand side of some multi-equation in M. SUBTERM((R,M)) is the union of SUBTERM(R) and SUBTERM(M). SUBTERM ' ((R, H)) is the union of SUBTERM' (R) and SUBTERM' (H).
Example.
SUBTERM( <x=l,y=f(z) >) = {l,f(z),z}. SUBTERM'(<x=l,y=f(z)>) = {z}. SUBTERM( { {x,y }=1, { z }=f( z), { u}="undef"}) {1, f( z), z, "undef"}. SUBTERM' ( { {x ,y }=l, {z)=f(z), {u}="undef" }) = {z}. SUBTERM(( <x=f(y) >, {{x,y}=f(y) })) = {f (y),y} . SUBTERM'((<x=f(y) >,{{x,y}=f(y)})) = {y}.
Definition. TERM(R) is the set of all nonvariable left or right hand side of some equation in R. TERM(M) is the set of all the right hand side of some multi-equation in M. TERM((R,M)) is the union of TERM(R) and TERM(M).
Example.
TERM( <x=f(x),y=z>) = {f (x)}. TERM({{x}=l,{y,z}=2}) = {1,2}. TERM(( <x=f(x),y=z>,{{x}=l,{y,z}=2})) {f ( x) , 1, 2} .
Let v, C and M be a variable, a variable class, and a set of multi-equations.
Definition. If there is a unique multi-equation in M of the form C=b for some b, we write BIND(C,M) for b. If there is a unique multi-equation, say C'=b', in M such that vis inC', we write CLASS (v,M) and VALUE(v,M) for C' and b'.
Example.
BIND({z,u},{{x,y}=l, {z ,u}=2,{v,w}=3}) = 2 . CLASS(z, {{x,y}=l,{z,u}=2,{v,w}=3}) {z,u}. VALUE(z,{{x,y}=l, {z,u}=2,{v,w}=3}) = 2.
III UNIFICATION ALGORITHM
An initial configuration of our algorithm is the form (R,M), where R is a system of input equa tions. Without loss of generality, we can suppose that 1) either right or left hand side of each equation in R is a variable, 2) for each variable v occurring in R or M, there is a unique variable class C occurring in M such that v is in C, and 3) the "undef" does not occur in R. Since our basic transformations defined below conserve the proper ties, we can suppose that these three conditions always hold.
Our unification process terminates if and only if the current R is empty, or FRONTIER operation defined below returns "clash". "clash" means the failure of the unification.
The primitive operations on trees(terms) in the unification process are to compute the "frontier" of two given terms and to test whether the one given term "is covered with" the other one .
Definition: Let t and u be terms. FRONTIER is the function which satisfies the following conditions.
- FRONTIER(t,u) = <t=u> if tor u is a variable.
- FRONTIER(f(tl,t2, ... ,tr),f(ul,u2, .. · ,ur))= Fl+F2+ ... +Fr. where r >=0, f is a functor, for each i (l=<i=<r), Fi=FRONTIER(ti ,ui) and Fi is not "clash" , and "+" is the concatenation operator for lists.
- FRONTIER(t.u) <> . i.e .· empty list if tor u is "undef".
- FRONTIER(t,u) "clash" otherwise .
Example .
FRONTIER(f(l,x),f(y, 2)) = <l=y,x=2>. FRONTIER(g(l),g(2)) ="clash".
Definition . For two given terms, t and u, we say t covers u if and only if:
- t is "undef" or
- u. is not "undef" and FRONTIER( t, u) <tl=vl,t2=v2, ... ,tr=vr> for some r>=0, where for each i (l=<i=<r) vi is a variable or atomic term.
Example.
f(g(l),2) covers f(x,y). f(x,y) is covered with f(g(l),2). f(x,g(y)) does not cover f(g(x) , y).
Remark . If a term tl is an instance of another term t 2, then tl covers t2. Therefore this rela tion is a generalization of the instance relation.
Given FRONTIER(tl,t2) , the time complexity to t est the covering relation between tl and t2 is only proportional to the length of the frontier.
Next, we will define basic transformations. Suppose the configuration (R,M) is given. The re sulting configuration (R',M') is defined as follows .
Let v=t or t=v be the top of R, where v is a variable and t is a term. Although the R-component of a configuration is used as either a stack or a queue in the algorithm, it is treated as a. set in the following definition for brevity.
Definition . Let (R,M) and (R',M') be two confi gu rations. We write (R,M)->(R',M') if and only if one of the following conditions holds.
RULEl : tis a variable, CLASS(v,M)=CLASS(t,M), M'=
M, and R'=R-{v=t}, where "-" is the difference operator for sets.
RULE2: t is a variable, CLASS(v,M) is not CLASS (t,M), M'=(M-{CLASS(v,M)=VALUE(v,M),CLASS(t,M)=
VALUE(t,M)}) U {C=z} , and R'=(R-{v=t}) U FRONTIER(VALUE(v,M),VALUE(t,M)), C=CLASS(v,M) U CLASS(t,M), and z is "undef" if both VALUE(v,M) and VALUE(t,M) are "undef'', otherwise any of them which is not "undef". RULE3 : t is not a variable , VALUE(v,M) is not covered with t, M'=(M-{CLASS(v ,M)=VALUE(v,M)}) U {CLASS(v ,M)=t }, and R'=(R-{v=t}) U FRONTIER(t,VALUE(v,M)).
RULE4 : t is not a variable, VALUE(v,M) is covered with t, M'=M and
R'=(R-{v=t}) U FRONTIER(t,VALUE(v,M)).
Example.
RULEl: (<x=y> , {{x,y}=l) - > ( <> , {{x,y}=l}) RULE2: ( <x=y>,{{x}="undef" , {y}=l}) - > ( <> , {{x,y} =1}) RULE3 : ( <x=f(y)> ,{ {x,y}=f(f(x))}) - > (<y=f(x) >, { {x , y}=f(y) }) RULE4: ( <x=f(f(x)) >,{{x,y}=f(y) }) - > ( <y=f(x) >, { {x,y}=f(y) })
Algorithm.
Input data: a configuration, say (R0,M0). Output data: "clash" or a set of multi-equa tions.
Method: 0) R=:R0 and M=:M0.
- if R is empty then return M.
- if (R,M)->(R',M') for some R' and M' then R=:R' and M=:M', otherwise return "clash".
- go to 1) . [ ]
Example. This example shows that the relation "is covered with" is essential for the termination of unification processes.
(<x=f(y ,f(g(y),x)),x=f(g(y),x) >, { {x.f="undef" , {y}="unde f"}) - >(<x=f(g(y) ,x) >, {{x}=f(y ,f(g(y),x)), {y}="undef"}) (RULE4) - >(<g(y)=y,x=f(g(y),x) >, { {x}=f(g(y) ,x), {y}="undef"}) (RULE3) - >(<x=f(g(y),x)>, {{x}=f(g(y) ,x),{y}=g(y)}) (RULE4) - >(<y=y,x=x> , {{x}=f(g(y) ,x), {y}=g(y)}) (RULE4) - >( <> , {{x}=f(g(y),x) , {y}=g(y)}) (RULEl,RULEl)
Remark. It is easy to check that if we do not re place the value in RULE3 above, the unification process does not terminate .
IV PROOF OF TERMINATION
I n this section, we treat a system of equa tions as a "queue" for convenience . Our proof for "stack" version is omitted here because it uses similar techniques fo r the "queue " version and is more lengthy .
Definition. We write (Rl,Ml)=>(R2,M2) if and only if the following conditions hold : (R2,M2) is obtained from (Rl ,Ml) by successive applications of bas ic transformations n ( >0) times, where n is the length of Rl .
Example .
( <x=y,y=z >, {{x}=f(x), {y}=f(y), {z}=f( z) }) => ( <x=y , x=z >, {{x , y ,z}=f(x)}).
Lemma 1. If (Rl,M)=>(R2,M) then TERM(R2) is a sub set of SUBTERM' (Rl)
Proof . From the definition of "=>", there exists a series of configurations ((Si , Ni) ;0=<i=<n) such that (SO,NO) - >(Sl,Nl)-> . .. - ) (Sn , Nn), where S0=Rl , N0=M, Nn=M, and n is the length of Rl.
Suppose there exists a term d in TERM(R2) but not in SUBTERM'(Rl) . Then, from the definition of "=>", we can select an integer j, a variable v, a term t, a variable class C, and a term b, satisfy ing all of the following condi tions: 1) l=<j=<n- 1, the top of Sj is either t=v or v=t, 2) v is in C, BIND(C,M)=b, BIND(C,Nj)=b, 3) b is not in TERM(Rl), b is not covered with t, 4) dis in TERM(FRONTIER(t,b)) .
From 2), and since b is not covered with t, BIND(C, N(j+l)) must be t. From 3), BIND(C,Ni) is not b fo r each i (j <i=<n). Since Nm=M, these imply that BIND(C,M) is not b. This ~s a contradiction to 2) . Therefore, TERM(R2) is a subset SUBTERM' (Rl). [ ]
Corollary 2 . There does not exist an infinite sequences of configurations ((Ri,M) ; i >=l) such that
(Rl,M) => (R2,M) => ... Pr oof . If the sequence exists, for any integer i >=l, TERM(R(i+l)) is a subset of SUBTERM'(Ri). But, it is impossible. []
Lemma 3. There does not exist an infinite sequences of configurations ((Ri,Mi);i>=l) such that all of t he following conditions hold:
- (Rl,Ml) => (R2,M2) => ... => (Rn,Mn) => ... ,
- for each k>=l and variable class C occurring in Mk, there exists such j (j >k) that BIND(C,Mj) is not BIND(C,Mk).
- Mi 's numbers of elements are equal to each other, i.e. no application of rule RULE2 appear in the sequence (i>=l).
Proof . From the infinite sequence above , we derive a contradiction. From 2), for any k there exists s uch j (k<j) that for any variable class C, the cardinality of the set {i ;k<i=<j, BIND(C,Mi) is not BIND(C,M(i-1))} is at least 2.
For each variable class C occurring in the sequence, let i(C) be the maximal integer i (i=<j) such that BIND(C ,Mi) is not BIND(C,Mj). From the condition for j, for each C, i(C) must be greate r thank , and BIND(C,Mj) is in TERM(Ri(C)) . Since for any i >k TERM(Ri) is a subset of SUBTERM ' ((Rk,Mk)),BIND(C,~) is in SUBTERM'((Rk,Mk)).
By successive applications of this process , we can build the sequence kl <k2< ... such that TERM((Rk(i+l\ Mk(i+l))) is a s ubset of SUBTERM'((Rk(i) ,Mk(i))) (i>=l). This is, as said before, impossible . [ ]
Theorem 4.4. There does not exist an infinite se quence such that
(Rl,Ml) => (R2,M2) => . .. => (Rn,Mn) => ...
Proof. We can prove this by induction with regard to the number of elements of Ml.
- Suppose that the number of elements of Ml is 1. Because of the corollary 1, there exis t no in t eger k>~l such that Mk=M(k+l)=M(k+2)= .... On the other hand, the lemma 2 says that it is impossible for Mi to change infinitely many times. So , the foundation is proved.
- Suppose that the number of elements of Ml is m+l, and that the theorem holds for the sequence such that the numbe r of the variable classes of the sequence is at most m.
If for some k>=l, the numbe r of the elements of Mk is less than that of M(k-1), then from the induction hypothesis, the sequence (Rk,Mk)=>(R(k+l),M(k+l)) => ... is finite. Then, the theorem holds in this case . Therefore, we suppose that the set of all variable classes occurring in Mi is independent of i (i>=l).
We derive a contradiction from the exis tence of the infinite sequence. For each i >=l, let Li be the set of all the common multi-equations in Mj (j >=i). And let L be the union of all Li (i>=l). Lis not empty because of lemma 2. Fix integer k>=l so that for all j >=k Lis a subset of Mj .
From the definitions of L and the basic transforma tions, TERM(Rj) is a subset of SUBTERM'((Rk,Mk-L)) fo r any j >k. By a similar method used in lemma 2 , we can construct the infinite sequence of integers k=<ll<l2<13< . .. such tha t TERM((Rl(i+l),Ml(i+l)-L)) is a subset of SUBTERM' ((Rl(i) ,Ml(i)-L)) (i>=l). But this is impossible, so the theorem is proved. [ ]
ACKNOWLEDGMENT
Kazuhiro Fuchi, Director of ICOT Research Cen ter, and Toshio Yokoi, Chief of 3rd Labolatory, in spired me in this work. I also want to thank my colleague , especially Dr. Takashi Chikayama, for their valuable comments.
@inproceedings{ijcai1983p131,
title = {A Unification Algorithm for Infinite Trees},
author = {Mukai, Kuniaki},
booktitle = {Proceedings of the Eighth International Joint Conference on
Artificial Intelligence, {IJCAI-83}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Alan Bundy},
pages = {547--548},
year = {1983},
note = {Logic Programming},
url = {https://ijcai.org/proceedings/1983/131},
}
TY - CPAPER TI - A Unification Algorithm for Infinite Trees AU - Mukai, Kuniaki T2 - Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83 PB - International Joint Conferences on Artificial Intelligence PY - 1983 SP - 547 EP - 548 UR - https://ijcai.org/proceedings/1983/131 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
Welcome
Future Conferences
AI Journal Division
IJCAI Proceedings
About IJCAI
IJCAI Awards