Abstract

For a hierarchy of properties of term rewriting systems related to confluence we prove relative undecidability: For implications X ⇒ Y in the hierarchy the property X is undecidable for term rewriting systems satisfying Y. For some of the implications either X or not X is semi-decidable, for others neither X nor not X is semi-decidable. We prove most of these results for linear term rewrite systems.

BibTeX Entry

@article{GMOZ-IC02b,
 author    = "Alfons Geser and Aart Middeldorp and Enno Ohlebusch and Hans
              Zantema",
 title     = "Relative Undecidability in the Term Rewriting, Part 2: The
              Confluence Hierarchy",
 journal   = "Information and Computation",
 volume    = 178,
 number    = 1,
 pages     = "132--148",
 year      = 2002,
 doi       = "10.1006/inco.2002.3150"
}