On the parameterized complexity of associative and commutative unification

DOI10.1016/j.tcs.2016.11.026zbMath1355.68108OpenAlexW1514995304MaRDI QIDQ729894

Takeyuki Tamura, Tatsuya Akutsu, Atsuhiro Takasu, Jesper Jansson

Publication date: 22 December 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.11.026

zbMATH Keywords

dynamic programmingunificationparameterized algorithmtree edit distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Uses Software

• HOL90
• BousiProlog

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey on tree edit distance and related problems
• Complexity of unification problems with associative-commutative operators
• Complexity of matching problems
• About the Paterson-Wegman linear unification algorithm
• Linear unification
• Adventures in associative-commutative unification
• The parameterized complexity of sequence alignment and consensus
• Single elementary associative-commutative matching
• Pattern matching with variables: a multivariate complexity analysis
• Parametrized complexity theory.
• On the computational power of pushdown automata
• Unification: a multidisciplinary survey
• A Unification Algorithm for Associative-Commutative Functions
• A Machine-Oriented Logic Based on the Resolution Principle
• Combinatorial Pattern Matching

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