de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Knuth-Bendix constraint solving is NP-complete

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44827

Korovin,  Konstantin
Programming Logics, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45678

Voronkov,  Andrei
Programming Logics, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Korovin, K., & Voronkov, A. (2005). Knuth-Bendix constraint solving is NP-complete. ACM Transactions on Computational Logic, 6, 361-388.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-26E6-5
Abstract
We 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.