Tight complexity bounds for term matching problems

DOI10.1016/0890-5401(92)90075-QzbMath0759.68040MaRDI QIDQ1201724

I. V. Ramakrishnan, Rakesh M. Verma

Publication date: 17 January 1993

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Related Items

Associative-commutative discrimination nets, Algorithms and reductions for rewriting problems. II.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching is as easy as matrix inversion
• Complexity of matching problems
• Subtree isomorphism is NC reducible to bipartite perfect matching
• Linear unification
• Automata-driven indexing of prolog clauses
• Simulation of Parallel Random Access Machines by Circuits
• A taxonomy of problems with fast parallel algorithms
• An Efficient Parallel Biconnectivity Algorithm
• On the sequential nature of unification
• Parallel Algorithms for Term Matching
• An Analysis of a Good Algorithm for the Subtree Problem, Corrected
• Finding the maximum, merging, and sorting in a parallel computation model
• An Analysis of a Good Algorithm for the Subtree Problem
• On Relating Time and Space to Size and Depth
• Term matching on parallel computers
• Parallelism in random access machines