English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 DetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AD5D-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AD5E-9
Genre: Journal Article

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Basin, David A.1, Author           
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Content

show
hide
Free keywords: -
 Abstract: 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

show
hide
Language(s): eng - English
 Dates: 2010-03-121994
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 519604
Other: Local-ID: C1256104005ECAFC-C0E7492EA342AC5BC125614400624895-Basin94c
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Information Processing Letters
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 51 (2) Sequence Number: - Start / End Page: 61 - 66 Identifier: ISSN: 0020-0190