TY - GEN
T1 - On the parameterized complexity of associative and commutative unification
AU - Akutsu, Tatsuya
AU - Jansson, Jesper Andreas
AU - Takasu, Atsuhiro
AU - Tamura, Takeyuki
PY - 2014/1/1
Y1 - 2014/1/1
N2 - 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 associativecommutative 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.
AB - 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 associativecommutative 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.
UR - http://www.scopus.com/inward/record.url?scp=84920026236&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-13524-3_2
DO - 10.1007/978-3-319-13524-3_2
M3 - Conference article published in proceeding or book
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 15
EP - 27
BT - Parameterized and Exact Computation - 9th International Symposium, IPEC 2014, Revised Selected Papers
PB - Springer Verlag
T2 - 9th International Symposium on Parameterized and Exact Computation, IPEC 2014
Y2 - 10 September 2014 through 12 September 2014
ER -