Tight complexity bounds for term matching problems

DOI10.1016/0890-5401(92)90075-QMaRDI QIDQ1201724zbMATH OpenFDO

Authors Rakesh M. Verma, I. V. Ramakrishnan

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)

Recommendations

• Complexity of matching problems
• scientific article; zbMATH DE number 3921983
• scientific article; zbMATH DE number 4090854
• On the sequential nature of unification
• Some complexity theoretic aspects of AC rewriting

Cites work

• scientific article; zbMATH DE number 4011929 (Why is no real title available?)
• scientific article; zbMATH DE number 4037157 (Why is no real title available?)
• scientific article; zbMATH DE number 4041265 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A taxonomy of problems with fast parallel algorithms
• An Analysis of a Good Algorithm for the Subtree Problem
• An Analysis of a Good Algorithm for the Subtree Problem, Corrected
• An Efficient Parallel Biconnectivity Algorithm
• Automata-driven indexing of prolog clauses
• Complexity of matching problems
• Finding the maximum, merging, and sorting in a parallel computation model
• Linear unification
• Matching is as easy as matrix inversion
• On Relating Time and Space to Size and Depth
• On the sequential nature of unification
• Parallel Algorithms for Term Matching
• Parallelism in random access machines
• Simulation of Parallel Random Access Machines by Circuits
• Subtree isomorphism is NC reducible to bipartite perfect matching
• Term matching on parallel computers

Cited in

(13)

• Single elementary associative-commutative matching
• Generating tables for bottom-up matching
• Some complexity theoretic aspects of AC rewriting
• Unification and matching on compressed terms
• Associative-commutative discrimination nets
• scientific article; zbMATH DE number 4090854 (Why is no real title available?)
• Algorithms and reductions for rewriting problems. II.
• scientific article; zbMATH DE number 4191126 (Why is no real title available?)
• scientific article; zbMATH DE number 1931655 (Why is no real title available?)
• Linear pattern matching of compressed terms and polynomial rewriting
• scientific article; zbMATH DE number 3921983 (Why is no real title available?)
• The complexity of linear and stratified context matching problems
• On the sequential nature of unification

This page was built for publication: Tight complexity bounds for term matching problems

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