Unification algorithm

In this section we illustrate our method on three different examples. Each example is chosen to demonstrate one particular aspect of the method. The first one shows that the generalization at the initial state is sufficient. Also, we give an outline of the unification algorithm of p-terms (Chen Hsiang 1995). The second one illustrates the use of rewriting rules to obtain a regular structure. For this example, it also suffices to generalize the initial state. 

The relation least element has been added [Lassez et al. 87]. The gib operator computes the gci (greatest common instance) of two terms (by a unification algorithm). The lub operator computes the msg of two terms (by an anti-unification algorithm). The msg of two terms thus always exists, and is unique up to variable renaming. 

L. -H. Eriksson. Synthesis of a unification algorithm in a logic programming calculus. 7. of Logic Programming l(l) 3-33, June 1984. 

Z. Manna and R. Waldinger. Deductive synthesis of the unification algorithm. Science of Computer Programming l 5-48, 1981. Also in [Biermann and Guiho 83], pp. 251-307. 

As said earlier, the concepts of msg and anti-unification were introduced simultaneously, but independently, by [Plotkin 70, 71] and [Reynolds 70]. The original motivation is accredited to [Popplestone 70], who suggested that since unification is useful in automatic deduction by the resolution method, its dual might prove helpful for induction . The main differences between both works are that Plotkin takes a logic-based approach and considers atomic formulas and clauses, whereas Reynolds is more concerned about an algebraic approach and only considers atomic formulas. But their results and msg algorithms are essentially the same. 

---