Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 DetailsÜbersicht
  A Term Equality Problem Equivalent to Graph Isomorphism

Basin, D. A. (1994). A Term Equality Problem Equivalent to Graph Isomorphism. Information Processing Letters, 51(2), 61-66.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AD5D-B Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AD5E-9
Genre: Zeitschriftenartikel

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Basin, David A.1, Autor           
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We demonstrate that deciding if two terms containing otherwise uninterpreted associative, commutative, and associative-commutative function symbols and commutative variable-binding operators are equal is polynomially equivalent to determining if two graphs are isomorphic. The reductions we use provide insight into this result and suggest polynomial time special cases.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-121994
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 519604
Anderer: Local-ID: C1256104005ECAFC-C0E7492EA342AC5BC125614400624895-Basin94c
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Information Processing Letters
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 51 (2) Artikelnummer: - Start- / Endseite: 61 - 66 Identifikator: ISSN: 0020-0190