Relative Undecidability in Term Rewriting

For a hierarchy of properties of term rewriting systems related to termination we prove relative undecidability: For implications X⇒Y in the hierarchy the property X is undecidable for term rewriting systems satisfying Y. For most implications we obtain this result for term rewriting systems consisting of a single rewrite rule.

Authors

• Alfons Geser
• Aart Middeldorp
• Enno Ohlebusch
• Hans Zantema

Keywords

No keywords are indexed for this paper.