Abstract

For a hierarchy of properties of term rewriting systems, related to termination, we prove relative undecidability even in the case of single rewrite rules: for implications X ⇒ Y in the hierarchy the property X is undecidable for rewrite rules satisfying Y.

BibTeX Entry

@inproceedings{GMOZ-CAAP97,
 author    = "Alfons Geser and Aart Middeldorp and Enno Ohlebusch and Hans
              Zantema",
 title     = "Relative Undecidability in the Termination Hierarchy of
              Single Rewrite Rules",
 booktitle = "Proceedings of the 22nd Colloquium on Trees in Algebra and
              Programming",
 series    = "Lecture Notes in Computer Science",
 volume    = 1214,
 pages     = "237--248",
 year      = 1997,
 doi       = "10.1007/BFb0030600"
}