Guo, Qing; Narendran, Paliath; Wolfram, David
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...[Show more]
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.