Complexity of Nilpotent Unification and Matching Problems

Abstract

We consider the complexity of equational unification and matching problems where the equational theory contains a nilpotent function, i.e., a function f satisfying f(x, x) = 0 where 0 is a constant. We show that nilpotent unification and matching are NP-complete. In the presence of associativity and commutativity, the problems still remain NP-complete. However, when 0 is also assumed to be the unity for the function f, the problems are solvable in polynomial time. We also show that the problem remains in P even when a homomorphism is added. An application of this result to a subclass of set constraints is illustrated. Second-order matching modulo nilpotence is shown to be undecidable. Show more