Abstract

We present two new transformation techniques for proving termination of context-sensitive rewriting. Our first method is simple, sound, and more powerful than previously suggested transformations. However, it is not complete, i.e., there are terminating context-sensitive rewrite systems that are transformed into non-terminating term rewrite systems. The second method that we present in this paper is both sound and complete. This latter result can be interpreted as stating that from a termination perspective there is no reason to study context-sensitive rewriting.

BibTeX Entry

@inproceedings{GM-RTA99,
 author    = "J{\"u}rgen Giesl and Aart Middeldorp",
 title     = "Transforming Context-Sensitive Rewrite Systems",
 booktitle = "Proceedings of the 10th International Conference on Rewriting
              Techniques and Applications",
 series    = "Lecture Notes in Computer Science",
 volume    = 1631,
 pages     = "271--285",
 year      = 1999,
 doi       = "10.1007/3-540-48685-2\_23"
}