Unification algorithms cannot be combined in polynomial time

DOI10.1007/3-540-61511-3_89zbMath1412.68233OpenAlexW2113396055MaRDI QIDQ4647521

Phokion G. Kolaitis, Miki Hermann

Publication date: 15 January 2019

Published in: Automated Deduction — Cade-13 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61511-3_89

zbMATH Keywords

counting problemequational theoryBoolean ringunification algorithmcombination algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

On the complexity of Boolean unification ⋮ Efficient general AGH-unification ⋮ Complexity of nilpotent unification and matching problems.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unification in Boolean rings and Abelian groups
• Unification in a combination of arbitrary disjoint equational theories
• The complexity of computing the permanent
• Unification in abelian semigroups
• Associative-commutative unification
• Unification in combinations of collapse-free regular theories
• Combining unification algorithms
• Combining symbolic constraint solvers on algebraic domains
• Complete sets of unifiers and matchers in equational theories
• Boolean unification - the story so far
• The complexity of counting problems in equational matching
• The Complexity of Enumeration and Reliability Problems
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• A Unification Algorithm for Associative-Commutative Functions
• Combination techniques for non-disjoint equational theories
• The complexity of theorem-proving procedures
• Computational complexity of simultaneous elementary matching problems

This page was built for publication: Unification algorithms cannot be combined in polynomial time