Context-Sensitive Dependency Pairs

Authors

Beatriz Alarcón, Raúl Gutiérrez, and Salvador Lucas

Abstract

Termination is one of the most interesting problems when dealing with context-sensitive rewrite systems. Although a good number of techniques for proving termination of context-sensitive rewriting (CSR) have been proposed so far, the adaptation to CSR of the dependency pair approach, one of the most powerful techniques for proving termination of rewriting, took some time and was possible only after introducing some new notions like collapsing dependency pairs, which are specific for CSR. In this paper, we develop the notion of context-sensitive dependency pair (CSDP) and show how to use CSDPs in proofs of termination of CSR. The implementation and practical use of the developed techniques yield a novel and powerful framework which improves the current state-of-the-art of methods for automatically proving termination of CSR.

Keywords

Dependency pairs, term rewriting, program analysis, termination.

Publication

Information and Computation, 208(8):922-968, August 2010.