Complexity of matching problems

DOI10.1016/S0747-7171(87)80027-5zbMath0638.68036MaRDI QIDQ1099615

Dan Benanav, Deepak Kapur, Paliath Narendran

Publication date: 1987

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

NP-completeassociative-commutative matching

Mathematics Subject Classification ID

Related Items (22)

Associative-commutative discrimination nets ⋮ An efficient labelled nested multiset unification algorithm ⋮ Unnamed Item ⋮ Unnecessary inferences in associative-commutative completion procedures ⋮ On the Parameterized Complexity of Associative and Commutative Unification ⋮ Optimization of rewriting and complexity of rewriting ⋮ A formalisation of nominal \(\alpha\)-equivalence with A, C, and AC function symbols ⋮ The complexity of counting problems in equational matching ⋮ From hidden to visible: a unified framework for transforming behavioral theories into rewrite theories ⋮ Term rewriting and beyond -- theorem proving in Isabelle ⋮ Partial derivatives of regular expressions and finite automaton constructions ⋮ Rewriting extended regular expressions ⋮ A formalisation of nominal \(\alpha\)-equivalence with A and AC function symbols ⋮ Complexity of unification problems with associative-commutative operators ⋮ Tight complexity bounds for term matching problems ⋮ Anti-patterns for rule-based languages ⋮ Variadic equational matching in associative and commutative theories ⋮ On the parameterized complexity of associative and commutative unification ⋮ Unification problem in equational theories ⋮ Certifying Term Rewriting Proofs in ELAN ⋮ A Folding Algorithm for Eliminating Existential Variables from Constraint Logic Programs ⋮ ELAN from a rewriting logic point of view

Uses Software

• RRL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New decision algorithms for finitely presented commutative semigroups
• Matching, unification and complexity
• Patterns and pattern-matching in trees: An analysis
• Parallel Algorithms for Term Matching
• A Unification Algorithm for Associative-Commutative Functions
• Pattern Matching in Trees
• Complete Sets of Reductions for Some Equational Theories
• Automated Theorem-Proving for Theories with Simplifiers Commutativity, and Associativity

This page was built for publication: Complexity of matching problems