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 -