Unification algorithms cannot be combined in polynomial time

DOI10.1007/3-540-61511-3_89MaRDI QIDQ4647521zbMATH OpenOpenAlexFDO

Authors Miki Hermann, Phokion G. Kolaitis

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

Boolean ringcombination algorithmcounting problemequational theoryunification algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Unification algorithms cannot be combined in polynomial time.
• Tractable and intractable instances of combination problems for unification and disunification
• A criterion for intractability of E-unification with free function symbols and its relevance for combination of unification algorithms
• scientific article; zbMATH DE number 4112560
• scientific article; zbMATH DE number 4049130

Cites work

• A Unification Algorithm for Associative-Commutative Functions
• Associative-commutative unification
• Boolean unification - the story so far
• Combination techniques for non-disjoint equational theories
• Combining symbolic constraint solvers on algebraic domains
• Combining unification algorithms
• Complete sets of unifiers and matchers in equational theories
• Computational complexity of simultaneous elementary matching problems
• scientific article; zbMATH DE number 4049025 (Why is no real title available?)
• scientific article; zbMATH DE number 4049130 (Why is no real title available?)
• scientific article; zbMATH DE number 1348479 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 3413831 (Why is no real title available?)
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• The complexity of computing the permanent
• The complexity of counting problems in equational matching
• The Complexity of Enumeration and Reliability Problems
• The complexity of theorem-proving procedures
• Unification in a combination of arbitrary disjoint equational theories
• Unification in abelian semigroups
• Unification in Boolean rings and Abelian groups
• Unification in combinations of collapse-free regular theories

Cited in

(8)

• Complexity of nilpotent unification and matching problems.
• Unification algorithms cannot be combined in polynomial time.
• On the complexity of Boolean unification
• scientific article; zbMATH DE number 4037063 (Why is no real title available?)
• scientific article; zbMATH DE number 2064226 (Why is no real title available?)
• A criterion for intractability of E-unification with free function symbols and its relevance for combination of unification algorithms
• Efficient general AGH-unification
• Tractable and intractable instances of combination problems for unification and disunification

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

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