Unification of Idempotent Functions
Proceedings of the Fifth International Joint Conference on Artificial Intelligence. Theorem Proving. Pages 528--1.
© 1977 International Joint Conferences on Artificial Intelligence
Abstract
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. Introduction
For almost as long as attempts at proving theorems by machines have been made, a critical problem has been well known: Equational axioms, if left with out precautions in the data base o f an automatic theorem prover (ATP), will force the ATP to ·go a stray.
Four approaches ~o cope with equality axioms have been proposed:
- To write the axioms into the data base, and use an additional rule of inference, such as paramodulation.
- To use special "rewrite rules".
- To design special inference rules incorporating these axioms.
- To develop special unification algorithms incorporating these axioms.
At least for equational axioms, the last approach (4) appears to be most promising.
So far we have concentrated on the axioms of asso ciativity, commutativity, idempotence and various combinations of these . In this paper, algorithms are presented for theories of idempotence and for idempotence together with commutativity. Idempotent functions appear in group theory, practical examp les being proofs about substitutions which are i dempotent if they are in normalform. See e . g. the proof of Theorem 3-2 in this paper. A historical example is how Luckham 's program verifier found the correctness of Robinson's unification algorithm on ly after the idempotence for unifiers had been ad ded.
The main results are that the unification problem for idempotence is decidable,and the set of all uni fiers is finite, but not a singleton in general.
2. Algorithm for I-Unification
2 . 1. Intuitive Overview. Our algorithm unifying two terms s and t is split up into two interlocking parts :
(1) Collapsing phase: In both s and t we look for subterms (r 1 ,r 2 l s.t. r 1 and r 2 can be unified by a substitution p to r . Then, applying p to s and t causes subterms (r 1 , r 2 ) to "collapse" to r, genera ting a new unification problem.
(2) R-unification phase: Unification problems resul ting from the collapsing phase are solved by the al gorithm RUNIFY . Essentially, RUNIFY follows the idea of Robinson's unification algorithm except for the way an atom and a non-atomic term is unified. (RUNIFY returns a success/failure message (SUCC/ FAI L) and a substitution (empty upon failure).) For space limitations we can not state the full algo rithms but the following examples may indicate the basic idea:
- s = f(f(a , x) , c) and t = f(x,c) has mgu 6={(x+a)}
- s = f(f(a,b) , f(z,d)) t = f(x , y) s has one collapse : f(f(a,b),d) {(z +d)} t has one collapse : y { (x + y)}
the unifiers are:
4
In a modified version of the algorithm 6 3 and 64, which are instances of 6 1 and 6 2 respectively, are not generated. However even the modified algorithm is not minimal in general.
3. Completeness of the Unification Algorithm The completeness of the unification algorithm IUNIFY is shown in two steps:
- First , we show that for any unifier 6 of terms s and t not collapsing any non-leaf nodes ("imme diate unifier"), RUNIFY applied to s and t success fully returns a unifier cr s.t. 6 ~ cr I.e . RUNIFY is complete w.r.t. immediate unifiers.
- We then show that for any arbitrary unifier cr of s and t we can find substitutions T and,- s.t .
TS is a collapse of s , and <'tis a collapse oft,
- TSEcollapse(s) and <'tEcollapse(t), and
- there is an immediate unifier 8 with 8Ts = 8T't and a 1:: 8eToT ' .
3.1. Partial Completeness of RUNIFY
Def.: For any term t, the set ICnode(t) of immedi atelY collapsable nodes in t is given by: For any k,labelling a node in the tree representation of t: If the largest subterm with root k is identical to ~subterm with a root being a brother to k , then kEICnode(t). Taking NLnode(t) to be the set of all non-leaf nodes in a term t, an immediate unifier is a substitution not immediately collapsing any non leaf nodes:
Def . : A unifier cr of two terms t 1 and t 2 is called an immediate unifier for t 1 and t2 iff
ICnode(crti)n NLnode(ti) = ¢ (i = 1 , 2).
To show the partial completeness of RUNIFY in Theo rem 3-2, we make use of the following lemma; Lemma 3-1. Let cr be an immediate unifier for two terms t 1 and t 2 , and disagree (t1,t2) = {s 1 ,s 2 }. Then cr 1 s = cr 2 s
Theorem 3-2 [Completeness of RUNIFY w. r . t.
Immediate Unifiers]
Let 6 be an immediate unifier of two terms t1 and t 2 . Then RUNIFY terminates successfully with RUNIFY t 1 t 2 = (SUCC,cr) and 6 !:cr.
3 . 2. Completeness of IUNIFY
To establish the overall completeness of the unifi cation algorithm,two auxiliary lemmas about substi tutions are needed:
Lemma 3-3. Let p and cr be substitutions with p ~ cr. Then, for any substitution T, p · T S: cr · T. Lemma 3-4. For any substitutions 6 , cr 1 , and cr 2 :
Theorem 3-5 . Let 6 be any unifier for two terms t 1 and t 2 . Then, there are substitutions <· 1 and T 2 s . t.
- T. t. is a collapse oft (i = 1,2) , and ~ ~ i
- RUNIFY applied to , 1 t 1 and T 2 t 2 successfully returns an immediate unifier 8 with 6 ': 8 o T 1 o T 2 ·
The completeness of IUNIFY is then an immediate consequence of Theorem 3-5.
@inproceedings{ijcai1977p120,
title = {Unification of Idempotent Functions},
author = {Kühner, Stefan and Mathis, Chris and Raulefs, Peter and Siekmann, Jörg H.},
booktitle = {Proceedings of the Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-77}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Raj Reddy},
pages = {528---1},
year = {1977},
note = {Theorem Proving},
url = {https://ijcai.org/proceedings/1977/120},
}
TY - CPAPER TI - Unification of Idempotent Functions AU - Kühner, Stefan AU - Mathis, Chris AU - Raulefs, Peter AU - Siekmann, Jörg H. T2 - Proceedings of the Fifth International Joint Conference on Artificial Intelligence, IJCAI-77 PB - International Joint Conferences on Artificial Intelligence PY - 1977 SP - 528 EP - -1 UR - https://ijcai.org/proceedings/1977/120 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: