The complexity of counting problems in equational matching
From MaRDI portal
Publication:5210797
DOI10.1007/3-540-58156-1_41zbMath1433.68171OpenAlexW2133259078MaRDI QIDQ5210797
Phokion G. Kolaitis, Miki Hermann
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
Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Equational classes, universal algebra in model theory (03C05)
Cites Work
- The complexity of computing the permanent
- On the complexity of recursive path orderings
- Complexity of unification problems with associative-commutative operators
- On unification: Equational theories are not bounded
- Termination of rewriting
- Complexity of matching problems
- Unification problems with one-sided distributivity
- 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\)
- Complete sets of unifiers and matchers in equational theories
- Boolean unification - the story so far
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item