Fast algorithms for uniform semi-unification
Uniform semi-unification is a simple combination of matching and unification defined as follows: given two terms s and t, do there exist substitutions ? and ? such that s??=t?? We present two algorithms for this problem based on Huets unification closure method, one producing (possibly) non-principal solutions, and one producing principal solutions. For both we provide a precise analysis of correctness and asymptotic complexity. Under the uniform cost RAM model (counting assignment, comparison, and arithmetic operations as primitive) our first algorithm is asymptotically as fast as Huets method, O(n?(n)), where ? is the functional inverse of Ackermanns function. Under a model which counts assignments and comparisons of pointers, and arithmetic operations on bits, the cost is O(n2?(n)2). Producing principal solutions is more complex, however, and our second algorithm runs in O(n2?(n)2) and under these two models.
algorithms semi-unification