Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2024) | last year (2023) | two years ago (2022) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Korovin, Konstantin
Voronkov, Andrei		dblp
dblp
Not MPG Author(s):
Voronkov, Andrei

BibTeX cite key*:

KorovinVoronkov:TOCL:2004

Title

Title*:

Knuth-Bendix constraint solving is NP-complete

Journal

Journal Title*:

ACM Transactions on Computational Logic
Journal's URL:

http://www.acm.org/tocl/

Download URL
for the article:

http://delivery.acm.org/10.1145/1060000/1055692/p361-korovin.pdf?key1=1055692&key2=1014020511&coll=GUIDE&dl=GUIDE&CFID=73538045&CFTOKEN=38481675
Language:

English

Publisher

Publisher's
Name:

ACM
Publisher's URL:

http://www.acm.org/

Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

6
Number:

2

Publishing Date:

2005

Pages*:

361-388
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:

http://doi.acm.org/10.1145/1055686.1055692

Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Programming Logics Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:
@ARTICLE{KorovinVoronkov:TOCL:2004,
AUTHOR = {Korovin, Konstantin and Voronkov, Andrei},
 TITLE = {{Knuth-Bendix} constraint solving is {NP-complete}},
 JOURNAL = {ACM Transactions on Computational Logic},
 PUBLISHER = {ACM},
 YEAR = {2005},
 NUMBER = {2},
 VOLUME = {6},
 PAGES = {361--388},
}

Entry last modified by Christine Kiesel, 01/28/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Konstantin Korovin		Created
01/23/2004 12:30:18 PM
Revisions
8.
7.
6.
5.
4.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Uwe Waldmann
Uwe Waldmann		Edit Dates
13.06.2006 15:12:46
13.06.2006 15:10:25
13.06.2006 15:09:11
03/23/2005 10:13:04 PM
02.02.2005 14:13:51