@ARTICLE{Basin94c,
AUTHOR        = "David A. Basin",
TITLE         = "A Term Equality Problem Equivalent to Graph Isomorphism",
YEAR          = 1994,
JOURNAL       = "Information Processing Letters",
VOLUME        = {51},
PAGES         = {61 -- 66},
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.  },
}