Abstract

For two hierarchies of properties of term rewriting systems related to confluence and termination, respectively, we prove relative undecidability: for implications X ⇒ Y in the hierarchies the property X is undecidable for term rewriting systems satisfying Y.

BibTeX Entry

@inproceedings{GMOZ-CSL96,
 author    = "Alfons Geser and Aart Middeldorp and Enno Ohlebusch and Hans
              Zantema",
 title     = "Relative Undecidability in Term Rewriting",
 booktitle = "Proceedings of the 10th Annual Conference of the
              European Association for Computer Science Logic",
 series    = "Lecture Notes in Computer Science",
 volume    = 1258,
 pages     = "150--166",
 year      = 1997,
 doi       = "10.1007/3-540-63172-0\_37"
}