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):

Krysta, Piotr
Pacholski, Leszek

dblp
dblp



BibTeX cite key*:

Krysta1999a

Title

Title*:

The STO problem is NP-complete

Journal

Journal Title*:

Journal of Symbolic Computation

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Academic Press

Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

27

Number:

2

Publishing Date:

February 1999

Pages*:

207-219

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

We prove that the problem STO of deciding whether or not a finite set $E$ of term equations is subject to occur check is in NP. $E$ is subject to occur check if an execution of the Martelli-Montanari unification algorithm gives for input $E$ a set $E^{\prime} \cup \{ x=t \}$, where $t \not= x$ and $x$ appears in $t$. Apt, van Emde Boas and Welling (1994) proved that STO is NP-hard leaving the problem of NP-completeness open.

URL for the Abstract:


Categories,
Keywords:

Unification Algorithms, NP-completeness, Data Structures

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:


Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat


BibTeX Entry:

@ARTICLE{Krysta1999a,
AUTHOR = {Krysta, Piotr and Pacholski, Leszek},
TITLE = {The STO problem is NP-complete},
JOURNAL = {Journal of Symbolic Computation},
PUBLISHER = {Academic Press},
YEAR = {1999},
NUMBER = {2},
VOLUME = {27},
PAGES = {207--219},
MONTH = {February},
}


Entry last modified by Uwe Brahm, 03/02/2010
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)
Piotr Krysta
Created
02/18/2000 07:39:31 PM
Revisions
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Piotr Krysta
Piotr Krysta
Piotr Krysta
Edit Dates
02/28/2001 06:46:21 PM
18/02/2000 19:39:31
21/04/99 13:26:46
21/04/99 13:12:01