Complexity of Deciding Syntactic Equivalence up to Renaming for Term Rewriting Systems (Extended Version)

Michael Christian Fink Amores, David Sabel

Motivated by questions from program transformations, eight notions of isomorphisms between term rewriting systems are defined, analysed, and classified. The notions include global…