On the parameterized complexity of associative and commutative unification
On the parameterized complexity of associative and commutative unification
复制标题
关于结合和交换统一的参数化复杂性
DOI：
10.1016/j.tcs.2016.11.026
复制
发表时间：
2017
影响因子：
1.1
通讯作者：
T. Tamura
中科院分区：
文献类型：
--
作者：
T. Akutsu;J. Jansson;A. Takasu;T. Tamura
本文研究了结合函数、交换函数和结合-交换函数的统一问题关于参数“变量数”的参数化复杂性。结果表明，如果每个变量只出现一次，则结合和结合交换统一问题都可以在多项式时间内求解，但在一般情况下，即使两个输入项中有一个是无变量的，这两个问题都是W [1]-困难的。对于交换统一，给出了一个时间复杂度与变量个数成指数关系的算法;此外，如果某个猜想成立，则其中一个输入项是无变量的特殊情况属于FPT。一些相关的结果也来自一个自然的推广的经典字符串和树编辑距离问题，允许变量。
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.