On the Parameterized Complexity of Associative and Commutative Unification

摘要

This paper studies the unification problem with associative, commutative, and associative-commutative functions. The parameterized complexity is analyzed with respect to the parameter "number of variables". It is shown that both the associative and associative-commutative unification problems are W[1]-hard. For commutative unification, a polynomial-time algorithm is presented in which the number of variables is assumed to be a constant. Some related results for the string and tree edit distance problems with variables are also presented.