Some complexity theoretic aspects of AC rewriting

DOI10.1007/BFB0029003MaRDI QIDQ5096174zbMATH OpenOpenAlexFDO

Authors Rakesh M. Verma, I. V. Ramakrishnan

Publication date 16 August 2022

Published in STACS 89 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0029003

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Recommendations

• Tight complexity bounds for term matching problems
• Computational complexity of simultaneous elementary matching problems
• Publication:3210184
• Single elementary associative-commutative matching
• Complexity of matching problems

Cites work

• An Analysis of a Good Algorithm for the Subtree Problem
• An Efficient Unification Algorithm
• scientific article; zbMATH DE number 3921983 (Why is no real title available?)
• scientific article; zbMATH DE number 4047099 (Why is no real title available?)
• scientific article; zbMATH DE number 4049127 (Why is no real title available?)
• scientific article; zbMATH DE number 4090854 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Linear unification
• Matching is as easy as matrix inversion
• On Relating Time and Space to Size and Depth
• Subtree isomorphism is NC reducible to bipartite perfect matching

Cited in

(5)

• Tight complexity bounds for term matching problems
• AC simplifications and closure redundancies in the superposition calculus
• scientific article; zbMATH DE number 3921983 (Why is no real title available?)
• scientific article; zbMATH DE number 2043518 (Why is no real title available?)
• Associative-commutative discrimination nets

This page was built for publication: Some complexity theoretic aspects of AC rewriting

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