Untyped Confluence In Dependent Type Theories: Full version

Abstract : We investigate techniques based on van Oostrom's decreasing diagrams that reduce confluence proofs to the checking of critical pairs in the absence of termination properties, which are useful in dependent type calculi to prove confluence on untyped terms. These techniques are applied to a complex example taken from practice: a faithful encoding in an extension of LF with rewrite rules on objects and types, of the calculus of constructions with a cumulative hierarchy of predicative universes above Prop. The rules may be first-order or higher-order, plain or modulo, non-linear on the right or on the left. Variables which occur non-linearly in lefthand sides of rules or in equations must take their values in confined types: in our example, the natural numbers. The first-order rules are assumed to be terminating and confluent modulo some theory: in our example, associativity, commutativity and identity. Critical pairs involving higher-order rules must satisfy van Oostrom's decreasing diagram condition with respect to their indexes taken as labels. Our use of decreasing diagrams yields a modular proof of confluence on open terms. Our encoding of the hierarchy of universes was obtained by using the MAUDE completion tool twisted to fit our needs. The obtained set of rules exploits all the sophistication of our confluence theorem.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Contributeur : Jean-Pierre Jouannaud <>
Soumis le : jeudi 27 avril 2017 - 15:41:59
Dernière modification le : jeudi 15 juin 2017 - 09:09:22


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01515505, version 1


Ali Assaf, Gilles Dowek, Jean-Pierre Jouannaud, Jiaxiang Liu. Untyped Confluence In Dependent Type Theories: Full version. 2017. <hal-01515505>



Consultations de
la notice


Téléchargements du document