Termination of rewrite relations on λλ-terms based on Girard's notion of reducibility

preprint2015arXivOpen access

Abstract

In this paper, we show how to extend the notion of reducibility introduced by Girard for proving the termination of ββ-reduction in the polymorphic λλ-calculus, to prove the termination of various kinds of rewrite relations on λλ-terms, including rewriting modulo some equational theory and rewriting with matching modulo ββηη, by using the notion of computability closure. This provides a powerful termination criterion for various higher-order rewriting frameworks, including Klop's Combinatory Reductions Systems with simple types and Nipkow's Higher-order Rewrite Systems.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.