The complexity of counting problems in equational matching

DOI10.1007/3-540-58156-1_41MaRDI QIDQ5210797zbMATH OpenOpenAlexFDO

Authors Miki Hermann, Phokion G. Kolaitis

Publication date 21 January 2020

Published in Automated Deduction — CADE-12 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58156-1_41

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Equational classes, universal algebra in model theory (03C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of counting problems in equational matching
• Single elementary associative-commutative matching
• Computational complexity of simultaneous elementary matching problems
• Computational complexity of simultaneous elementary matching problems
• scientific article; zbMATH DE number 3921983

Cites work

• A technical note on AC-unification. The number of minimal unifiers of the equation \(\alpha x_ 1+ \cdots + \alpha x_ p \doteq _{AC} \beta y_ 1+ \cdots + \beta y_ q\)
• Boolean unification - the story so far
• Complete sets of unifiers and matchers in equational theories
• Complexity of matching problems
• Complexity of unification problems with associative-commutative operators
• scientific article; zbMATH DE number 4049047 (Why is no real title available?)
• scientific article; zbMATH DE number 3778778 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 3413831 (Why is no real title available?)
• On the complexity of recursive path orderings
• On unification: Equational theories are not bounded
• Termination of rewriting
• The complexity of computing the permanent
• Unification problems with one-sided distributivity

Cited in

(3)

• The complexity of counting problems in equational matching
• The Complexity of Counting Quantifiers on Equality Languages
• Computational complexity of simultaneous elementary matching problems

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 Q5210797)