Termination of context-sensitive rewriting by rewriting

Author

Salvador Lucas

Abstract

Context-sensitive rewriting allows us to deal with certain context-replacing restrictions in performing reduction steps. This is useful in avoiding undesirable reductions. In this paper, we study termination of context-sensitive rewriting. We give some conditions under which it is possible to analyze the termination of the context-sensitive rewrite relation induced by a term rewriting system by means of standard methods to prove termination of rewriting. This allows us to apply all known (and forthcoming) results on termination to context-sensitive rewriting.

Keywords

term rewriting systems, regularity, functional programming, termination.