The Simply-typed Pure Pattern Type System Ensures Strong Normalization

Benjamin Wack 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Pure Pattern Type Systems (PPTS) combine in a unified setting the capabilities of rewriting and lambda-calculus. Their type systems, adapted from Barendregt's lambda-cube, are especially interesting from a logical point of view. Strong normalization, an essential property for logical soundness, had only been conjectured so far: in this paper, we give a positive answer for the simply-typed system. The proof is based on a translation of terms and types from PPTS into the lambda-calculus. First, we deal with untyped terms, ensuring that reductions are faithfully mimicked in the lambda-calculus. For this, we rely on an original encoding of the pattern matching capability of PPTS into the lambda-calculus. Then we show how to translate types: the expressive power of System F omega is needed in order to fully reproduce the original typing judgments of PPTS. We prove that the encoding is correct with respect to reductions and typing, and we conclude with the strong normalization of simply-typed PPTS terms.
Type de document :
Communication dans un congrès
Jean-Jacques Lévy. 3rd IFIP International Conference on Theoretical Computer Science - TCS'2004, 2004, Toulouse, France, Kluwer Academic Publishers, pp.633-646, 2004
Liste complète des métadonnées

https://hal.inria.fr/inria-00100109
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:14:12
Dernière modification le : jeudi 11 janvier 2018 - 06:19:57

Identifiants

  • HAL Id : inria-00100109, version 1

Collections

Citation

Benjamin Wack. The Simply-typed Pure Pattern Type System Ensures Strong Normalization. Jean-Jacques Lévy. 3rd IFIP International Conference on Theoretical Computer Science - TCS'2004, 2004, Toulouse, France, Kluwer Academic Publishers, pp.633-646, 2004. 〈inria-00100109〉

Partager

Métriques

Consultations de la notice

74