Guo, QingNarendran, PaliathWolfram, David2015-12-130890-5401http://hdl.handle.net/1885/89088We 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.Keywords: Algorithms; Linear equations; Pattern matching; Polynomials; Problem solving; Set theory; Matching problems; Computational complexity200010.1006/inco.1999.28492015-12-12