A decision algorithm for distributive unification
The purpose of this paper is to describe a decision algorithm for unifiability of equations w.r.t. the equational theory D of two distributive axioms: x *(y + z) = x * y + x * z and (x + y)*z = x * z + y * z. The algorithm is described as a set of non-deterministic transformation rules. The equations given as input are eventually transformed into an ACI-unification-problem with linear constant restrictions. Since the algorithm terminates, this is a solution for an open problem in the field of unification and shows decidability of D-unification. One spin-off is an algorithm that decides the word-problem w.r.t. D in polynomial time. This is the basis for an NP-algorithm for D-matching, hence D-matching is NP-complete. A further (future) spin-off is a decision algorithm for stratified context unification problems. (C) 1998-Elsevier Science B.V. All rights reserved.
distributive unification unification context unification equational unification distributive matching