Knuth-Bendix constraint solving is NP-complete

Simple item page
dc.creatorKorovin, Konstantin
dc.creatorVoronkov, Andrei
dc.date2002-07-17
dc.date.accessioned2026-07-07T03:18:42Z
dc.date.available2026-07-07T03:18:42Z
dc.descriptionWe show the NP-completeness of the existential theory of term algebras with the Knuth-Bendix order by giving a nondeterministic polynomial-time algorithm for solving Knuth-Bendix ordering constraints.
dc.description27 pages
dc.identifierhttps://arxiv.org/abs/cs/0207068
dc.identifierhttp://arxiv.org/abs/cs/0207068
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31218
dc.subjectLogic in Computer Science
dc.subjectF.4.1
dc.titleKnuth-Bendix constraint solving is NP-complete
dc.typetext

Files

Collections

arXiv