published by Konstantin Korovin
in 2002
in Informatics Engineering
and research's language is
English
Download
Abstract in English
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.