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-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.
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||9th International Symposium on Parameterized and Exact Computation, IPEC 2014|
|Period||10/09/14 → 12/09/14|
- Theoretical Computer Science
- Computer Science(all)