On the parameterized complexity of associative and commutative unification

DOI10.1007/978-3-319-13524-3_2zbMATH Open1456.68061arXiv1310.0919OpenAlexW2726068116MaRDI QIDQ2946004FDOQ2946004

Authors: Tatsuya Akutsu, Jesper Jansson, Atsuhiro Takasu, Takeyuki Tamura 

Publication date: 15 September 2015

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Abstract: This paper studies the unification problem with associative, commutative, and associative-commutative functions mainly from a viewpoint of the parameterized complexity on the number of variables. It is shown that both associative and associative-commutative unification problems are $W[1]$-hard. A fixed-parameter algorithm and a polynomial-time algorithm are presented for special cases of commutative unification in which one input term is variable-free and the number of variables is bounded by a constant, respectively. Related results including those on the string and tree edit distance problems with variables are shown too.

Full work available at URL: https://arxiv.org/abs/1310.0919

Recommendations

• On the parameterized complexity of associative and commutative unification
• Complexity of unification problems with associative-commutative operators
• Associative-commutative unification
• An algebraic approach to unification under associativity and commutativity
• scientific article; zbMATH DE number 3930337

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Title not available (Why is that?)
• Parametrized complexity theory.
• Unification theory
• A survey on tree edit distance and related problems
• Linear unification
• A Machine-Oriented Logic Based on the Resolution Principle
• Unification: a multidisciplinary survey
• Pattern Matching with Variables: A Multivariate Complexity Analysis
• Complexity of matching problems
• The parameterized complexity of sequence alignment and consensus
• About the Paterson-Wegman linear unification algorithm
• Single elementary associative-commutative matching
• Combinatorial Pattern Matching

Cited In (5)

• On the parameterized complexity of associative and commutative unification
• Complexity of unification problems with associative-commutative operators
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: On the parameterized complexity of associative and commutative unification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946004)