The complexity of counting problems in equational matching

DOI10.1006/JSCO.1995.1054MaRDI QIDQ1914166zbMATH OpenOpenAlexFDO

Authors Miki Hermann, Phokion G. Kolaitis

Publication date 13 August 1996

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

Full work available at URL https://doi.org/10.1006/jsco.1995.1054

zbMATH Keywords

computational complexityequational matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of counting problems in equational matching
• Computational complexity of simultaneous elementary matching problems
• Computational complexity of simultaneous elementary matching problems
• scientific article; zbMATH DE number 3921983
• Complexity of matching problems

Cited in

(7)

• Unification algorithms cannot be combined in polynomial time.
• The Complexity of Counting Quantifiers on Equality Languages
• Unification algorithms cannot be combined in polynomial time
• The complexity of counting problems in equational matching
• Computational complexity of simultaneous elementary matching problems
• Regular expression order-sorted unification and matching
• Anti-patterns for rule-based languages

This page was built for publication: The complexity of counting problems in equational matching

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