کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952276 | 1442029 | 2017 | 18 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On the parameterized complexity of associative and commutative unification On the parameterized complexity of associative and commutative unification](/preview/png/4952276.png)
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 W[1]-hard even when one of the two input terms is variable-free. For commutative unification, an algorithm whose time complexity depends exponentially on the number of variables is presented; 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.
Journal: Theoretical Computer Science - Volume 660, 17 January 2017, Pages 57-74