JavaScript is disabled for your browser. Some features of this site may not work without it.
Equality of Terms Containing Associative-Commutative Functions and Commutative Binding Operators is Isomorphism Complete

Author
Basin, David A.
Abstract
We demonstrate that deciding if two terms containing uninterpreted 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.
Date Issued
1989-06Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1020
Type
technical report