Lazy Linear Combinatorial Unification

AbstractIn this paper we define a two-rule reduction system for the lazy computation of unification on first-order terms. The computation consists of a sequence of reductions which is almost linear with the size of the input. Every reduction transforms the problem into an equivalent one which is a better approximation of the solution. The approach is based on a combinatorial system which provides abstractions for terms and term unification, and does not resort to any specific reduction control strategy. The abstraction on both data and control makes our system suitable in any applicative context where unification is required