This article studies the parameterized complexity of the unification problem with associative, commutative, or associative-commutative functions with respect to the parameter “number of variables”. It is shown that if every variable occurs only once then both of the associative and associative-commutative unification problems can be solved in polynomial time, but that in the general case, both problems are  <span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516306892&_mathId=si1.gif&_user=111111111&_pii=S0304397516306892&_rdoc=1&_issn=03043975m moreover, if a certain conjecture is true then the special case where one input term is variable-free belongs to FPT. Some related results are also derived for a natural generalization of the classic string and tree edit distance problems that allows variables.
['Tatsuya Akutsu', 'Jesper Jansson', 'Atsuhiro Takasu', 'Takeyuki Tamura']
On the parameterized complexity of associative and commutative unification