Degrees of Undecidability in Rewriting

Joerg Endrullis, Herman Geuvers, Hans Zantema

Undecidability of various properties of first order term rewriting systems is well-known. An undecidable property can be classified by the complexity of the formula defining it. Th…