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.
展开▼