Proceedings

Unification of Idempotent Functions

Download BibTeX Cite

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:

  1. To write the axioms into the data base, and use an additional rule of inference, such as paramodulation.
  2. To use special "rewrite rules".
  3. To design special inference rules incorporating these axioms.
  4. 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:

  1. s = f(f(a , x) , c) and t = f(x,c) has mgu 6={(x+a)}
  2. 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:

Formula not decoded
Formula not decoded

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:

  1. 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.
  2. 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,

  1. TSEcollapse(s) and <'tEcollapse(t), and
  2. 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 :

Formula not decoded

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.

  1. T. t. is a collapse oft (i = 1,2) , and ~ ~ i
  2. 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.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards