On the parameterized complexity of associative and commutative unification

Tatsuya Akutsu, Jesper Andreas Jansson, Atsuhiro Takasu, Takeyuki Tamura

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)57-74
Number of pages18
JournalTheoretical Computer Science
Volume660
DOIs
Publication statusPublished - 17 Jan 2017
Externally publishedYes

Keywords

  • Dynamic programming
  • Parameterized algorithm
  • Tree edit distance
  • Unification

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this