Knuth--bendix constraint solving is NP-complete

DOI10.1145/1055686.1055692zbMATH Open1367.68104OpenAlexW2021951582WikidataQ130947745 ScholiaQ130947745MaRDI QIDQ5277725

Andrei Voronkov, Konstantin Korovin

Publication date: 12 July 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1055686.1055692

zbMATH Keywords

automated deductionKnuth-Bendix ordersordering constraints

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Tatamibari is NP-complete ⋮ Solving the Rubik's Cube Optimally is NP-complete ⋮ Rikudo is NP-complete

This page was built for publication: Knuth--bendix constraint solving is NP-complete

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