Rewriting Modulo β in the λ Π-Calculus Modulo

Abstract : The λ Π-calculus Modulo is a variant of the λ-calculus with dependent types where β-conversion is extended with user-defined rewrite rules. It is an expressive logical framework and has been used to encode logics and type systems in a shallow way. Basic properties such as subject reduction or uniqueness of types do not hold in general in the λ Π-calculus Modulo. However, they hold if the rewrite system generated by the rewrite rules together with β-reduction is confluent. But this is too restrictive. To handle the case where non confluence comes from the interference between the β-reduction and rewrite rules with λ-abstraction on their left-hand side, we introduce a notion of rewriting modulo β for the λ Π-calculus Modulo. We prove that confluence of rewriting modulo β is enough to ensure subject reduction and uniqueness of types. We achieve our goal by encoding the λ Π-calculus Modulo into Higher-Order Rewrite System (HRS). As a consequence, we also make the confluence results for HRSs available for the λ Π-calculus Modulo.
Type de document :
Communication dans un congrès
Logical Frameworks and Meta Languages: Theory and Practic, Affiliated with CADE-25, Aug 2015, Berlin, Germany. 185, pp 87-101, Electronic Proceedings in Theoretical Computer Science. 〈 http://eptcs.web.cse.unsw.edu.au/content.cgi?LFMTP15〉. 〈10.4204/EPTCS.185.6〉
Liste complète des métadonnées

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

https://hal-mines-paristech.archives-ouvertes.fr/hal-01176715
Contributeur : Claire Medrala <>
Soumis le : mercredi 15 juillet 2015 - 17:11:27
Dernière modification le : lundi 12 novembre 2018 - 11:02:04
Document(s) archivé(s) le : mercredi 26 avril 2017 - 05:43:48

Fichier

A-610.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Ronan Saillard. Rewriting Modulo β in the λ Π-Calculus Modulo. Logical Frameworks and Meta Languages: Theory and Practic, Affiliated with CADE-25, Aug 2015, Berlin, Germany. 185, pp 87-101, Electronic Proceedings in Theoretical Computer Science. 〈 http://eptcs.web.cse.unsw.edu.au/content.cgi?LFMTP15〉. 〈10.4204/EPTCS.185.6〉. 〈hal-01176715〉

Partager

Métriques

Consultations de la notice

287

Téléchargements de fichiers

93