Knuth-Bendix constraint solving is NP-complete

Korovin, Konstantin; Voronkov, Andrei

Local TagsRelease HistoryDetailsSummary

Knuth-Bendix constraint solving is NP-complete

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

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-26E6-5 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-26E7-3

Genre: Journal Article

Files

show Files

Locators

show

Creators

show

hide

Creators:
Korovin, Konstantin¹, Author
Voronkov, Andrei¹, Author

Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045

Content

show

hide

Free keywords: -

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.

Details

show

hide

Language(s): eng - English

Dates: Modified: 2006-06-13Date issued: 2005

Publication Status: Issued

Pages: -

Publishing info: -

Table of Contents: -

Rev. Type: Peer

Identifiers: eDoc: 279120
Other: Local-ID: C1256104005ECAFC-A909D96B3210A3E9C1256E24003F32EB-KorovinVoronkov:TOCL:2004

Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show

hide

Title: ACM Transactions on Computational Logic

Source Genre: Journal

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: 6 Sequence Number: - Start / End Page: 361 - 388 Identifier: -