Paper Info
Title
Knuth-Bendix Constraint Solving Is NP-Complete
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.
Year
DOI
Venue
2005
10.1145/1055686.1055692
ACM Transactions on Computational Logic (TOCL)
Keywords
DocType
Volume
Knuth-Bendix order,existential theory,nondeterministic polynomial-time algorithm,term algebra,Knuth-Bendix Constraint
Journal
6
Issue
ISSN
ISBN
2
0302-9743
3-540-42287-0
Citations 
PageRank 
References 
12
1.11
29
Authors
2
Name
Order
Citations
PageRank
Konstantin Korovin128820.64
Andrei Voronkov22670225.46