Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | 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