Complexity of unification problems with associative-commutative operators
From MaRDI portal
Publication:688565
DOI10.1007/BF00245463zbMATH Open0781.68076MaRDI QIDQ688565FDOQ688565
Authors: Deepak Kapur, Paliath Narendran 
Publication date: 20 December 1993
Published in: Journal of Automated Reasoning (Search for Journal in Brave)
Recommendations
- On the parameterized complexity of associative and commutative unification
- On the parameterized complexity of associative and commutative unification
- Associative-commutative unification
- scientific article; zbMATH DE number 3871322
- Adventures in associative-commutative unification
- scientific article; zbMATH DE number 4074540
- An algebraic approach to unification under associativity and commutativity
- scientific article; zbMATH DE number 3930337
- Unifications, deunifications, and their complexity
- Complexity of nilpotent unification and matching problems.
matchingidempotentNP-completeunitword equationsunificationidentityequational theoriesassociativecommutativeset matching
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Linear unification
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Unification Algorithm for Associative-Commutative Functions
- Complete Sets of Reductions for Some Equational Theories
- Title not available (Why is that?)
- THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Complexity of matching problems
- Unification problems with one-sided distributivity
- Automated Theorem-Proving for Theories with Simplifiers Commutativity, and Associativity
- Title not available (Why is that?)
- Unification in varieties of idempotent semigroups
- Unification theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- Matching, unification and complexity
- Title not available (Why is that?)
Cited In (30)
- Unification algorithms cannot be combined in polynomial time.
- Combination techniques and decision problems for disunification
- On the parameterized complexity of associative and commutative unification
- Cancellative Abelian monoids and related structures in refutational theorem proving. I
- On the unification problem for Cartesian closed categories
- Unification theory
- A formalisation of nominal C-matching through unification with protected variables
- Title not available (Why is that?)
- Complexity of nilpotent unification and matching problems.
- \(E\)-unification with constants vs. general \(E\)-unification
- AC-superposition with constraints: No AC-unifiers needed
- Generating languages by a derivation procedure for elementary formal systems
- Unification and matching modulo nilpotence
- What Is Essential Unification?
- More problems in rewriting
- An algorithm for distributive unification
- Title not available (Why is that?)
- NP-completeness results for deductive problems on stratified terms
- Formalising nominal C-unification generalised with protected variables
- The complexity of counting problems in equational matching
- An efficient labelled nested multiset unification algorithm
- Extensions of unification modulo ACUI
- Extending Unification in $\mathcal{EL}$ to Disunification: The Case of Dismatching and Local Disunification
- Approximate Unification in the Description Logic $$\mathcal {FL}_0$$
- Title not available (Why is that?)
- On complexity of the anti-unification problem
- Variant-Based Satisfiability in Initial Algebras
- Type dependencies for logic programs using ACI-unification
- Title not available (Why is that?)
- Combination techniques and decision problems for disunification
This page was built for publication: Complexity of unification problems with associative-commutative operators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688565)
