Unification algorithms cannot be combined in polynomial time.

DOI10.1006/inco.1999.2855zbMath1045.68568OpenAlexW1993506583MaRDI QIDQ1854364

Miki Hermann, Phokion G. Kolaitis

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/f5a30dabff8370f7b60acf2643de2d0ad433fe4b

zbMATH Keywords

counting problemscomplexity class

Mathematics Subject Classification ID

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Complexity of unification problems with associative-commutative operators
• Unification in abelian semigroups
• Associative-commutative unification
• Unification in combinations of collapse-free regular theories
• Unification in Boolean rings
• Combining matching algorithms: The regular case
• 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
• Combining decision algorithms for matching in the union of disjoint equational theories
• Unification in the union of disjoint equational theories: Combining decision procedures
• 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
• Unification and matching modulo nilpotence
• Combination of constraint solving techniques: An algebraic point of view
• 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.