Knuth-Bendix constraint solving is NP-complete

DOI10.1007/3-540-48224-5_79MaRDI QIDQ4535077zbMATH OpenFDO

Authors Konstantin Korovin, Andrei Voronkov

Publication date 12 June 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2076/20760979

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Cited in

(10)

• Orienting rewrite rules with the Knuth-Bendix order.
• Rikudo is NP-complete
• Decision procedures for term algebras with integer constraints
• Solving the Rubik's Cube Optimally is NP-complete
• Tatamibari is NP-complete
• KBO Constraint Solving Revisited
• Term ordering diagrams
• Partial redundancy in saturation
• Reducibility constraints in superposition
• Superposition-based equality handling for analytic tableaux

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