Termination of higher-order rewrite systems based on the notion of computability closure

In this paper, we show how the notion of computability introduced by W. W. Tait and extended to polymorphic types by J.-Y. Girard can be used and easily extended to prove the termination of various kind of rewriting relations on lambda-terms, including matching on defined symbols, higher-order matching or class-rewriting modulo some equational theories. We also show how the notion of computability closure can easily be turned into a well-founded relation including J.-P. Jouannaud and A. Rubio's higher-order extension of N. Dershowitz' recursive path ordering.

Data and Resources

Additional Info

Field Value
Source https://theses.hal.science/tel-00724233
Author Blanqui, Frédéric
Maintainer CCSD
Last Updated November 4, 2026, 04:07 (UTC)
Created November 4, 2026, 04:07 (UTC)
Identifier tel-00724233
Language fr
Rights https://about.hal.science/hal-authorisation-v1/
contributor Formal Methods for Embedded Systems (FORMES) ; Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées (LIAMA) ; Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Chinese Academy of Sciences [Changchun Branch] (CAS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institute of Automation - Chinese Academy of Sciences-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt ; Institut National de Recherche en Informatique et en Automatique (Inria)
creator Blanqui, Frédéric
date 2012-07-13T00:00:00
harvest_object_id 6866acd5-63c9-4555-b606-aa45324c1f90
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-03-21T00:00:00
set_spec type:HDR