Combining typing and size constraints for checking the termination of higher-order conditional rewrite systems

Frédéric Blanqui 1 Colin Riba 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In a previous work, the first author extended to higher-order rewriting and dependent types the use of size annotations in types, a termination proof technique called type or size based termination and initially developed for ML-like programs. Here, we go one step further by considering conditional rewriting and explicit quantifications and constraints on size annotations. This allows to describe more precisely how the size of the output of a function depends on the size of its inputs. Hence, we can check the termination of more functions. We first give a general type-checking algorithm based on constraint solving. Then, we give a termination criterion with constraints in Presburger arithmetic. To our knowledge, this is the first termination criterion for higher-order conditional rewriting taking into account the conditions in termination.
Type de document :
Communication dans un congrès
13th International Conference on Logic for Programming, Artificial Intelligence and Reasoning - LPAR 2006, Nov 2006, Phnom Penh, Cambodia. 4246, 2006, LNCS. 〈10.1007/11916277_8〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00084837
Contributeur : Frédéric Blanqui <>
Soumis le : lundi 11 septembre 2006 - 13:38:18
Dernière modification le : jeudi 8 février 2018 - 11:32:01
Document(s) archivé(s) le : lundi 20 septembre 2010 - 16:55:44

Fichiers

Identifiants

Collections

Citation

Frédéric Blanqui, Colin Riba. Combining typing and size constraints for checking the termination of higher-order conditional rewrite systems. 13th International Conference on Logic for Programming, Artificial Intelligence and Reasoning - LPAR 2006, Nov 2006, Phnom Penh, Cambodia. 4246, 2006, LNCS. 〈10.1007/11916277_8〉. 〈inria-00084837v2〉

Partager

Métriques

Consultations de la notice

182

Téléchargements de fichiers

73