On the parameterized complexity of associative and commutative unification

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationParameterized and Exact Computation - 9th International Symposium, IPEC 2014, Revised Selected Papers
PublisherSpringer Verlag
Pages15-27
Number of pages13
ISBN (Electronic)9783319135236
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event9th International Symposium on Parameterized and Exact Computation, IPEC 2014 - Wroclaw, Poland
Duration: 10 Sep 201412 Sep 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8894
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Symposium on Parameterized and Exact Computation, IPEC 2014
CountryPoland
CityWroclaw
Period10/09/1412/09/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this