Open AccessEquality of terms containing associative-commutative functions and commutative binding operators is isomorphism complete
Author(s) -
David Basin
Publication year - 1990
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
ISBN - 3-540-52885-7
DOI - 10.1007/3-540-52885-7_92
Subject(s) - commutative property , associative property , isomorphism (crystallography) , function (biology) , polynomial , mathematics , algebra over a field , computer science , discrete mathematics , pure mathematics , mathematical analysis , chemistry , evolutionary biology , crystal structure , biology , crystallography
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom