NP-completeness results for deductive problems on stratified terms

zbMATH Open1273.68316MaRDI QIDQ3408147FDOQ3408147

Authors Thierry Boy de la Tour, Mnacho Echenim 

Publication date 24 February 2010

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mechanization of proofs and logical operations (03B35)

Recommendations

• On the complexity of deduction modulo leaf permutative equations
• On leaf permutative theories and occurrence permutation groups
• Term Rewriting and Applications
• Stratified Context Unification Is NP-Complete
• Complexity of unification problems with associative-commutative operators

Cited in

(3)

• On strong NP-completeness of rational problems
• On the complexity of deduction modulo leaf permutative equations
• Stratified Context Unification Is NP-Complete

This page was built for publication: NP-completeness results for deductive problems on stratified terms

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