Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  The STO problem is NP-complete

Krysta, P., & Pacholski, L. (1999). The STO problem is NP-complete. Journal of Symbolic Computation, 27(2), 207-219.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3619-C Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-361A-A
Genre: Zeitschriftenartikel

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Krysta, Piotr1, Autor           
Pacholski, Leszek2, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-021999
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 518128
Anderer: Local-ID: C1256428004B93B8-1CC0C7E2A4CD9515C125688900667F07-Krysta1999a
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Journal of Symbolic Computation
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 27 (2) Artikelnummer: - Start- / Endseite: 207 - 219 Identifikator: -