A unification algorithm for typed λ-calculus

AbstractA semi-decision algorithm is presented, to search for unification of formulas in typed ω-order λ-calculus, and its correctness is proved.It is shown that the search space is significantly smaller than the one for finding the most general unifiers. In particular, our search is not redundant. This allows our algorithm to have good directionality and convergence properties