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. © 2011 Springer-Verlag Berlin Heidelberg.
| Original language | English |
|---|---|
| Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci. |
| Publisher | Springer Nature |
| Pages | 979-992 |
| Number of pages | 13 |
| Volume | 2076 |
| ISBN (Print) | 3540422870, 9783540422877 |
| Publication status | Published - 2001 |
| Event | 28th International Colloquium on Automata, Languages and Programming, ICALP 2001 - Crete Duration: 1 Jul 2001 → … http://dblp.uni-trier.de/db/conf/icalp/icalp2001.html#KorovinV01http://dblp.uni-trier.de/rec/bibtex/conf/icalp/KorovinV01.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/icalp/KorovinV01 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|
Conference
| Conference | 28th International Colloquium on Automata, Languages and Programming, ICALP 2001 |
|---|---|
| City | Crete |
| Period | 1/07/01 → … |
| Internet address |