Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Claire Medrala Connect in order to contact the contributor
Submitted on : Wednesday, July 15, 2015 - 5:11:27 PM
Last modification on : Monday, June 27, 2022 - 3:07:00 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 5:43:48 AM


Files produced by the author(s)



Ronan Saillard. Rewriting Modulo β in the λ Π-Calculus Modulo. Logical Frameworks and Meta Languages: Theory and Practic, Affiliated with CADE-25, Aug 2015, Berlin, Germany. pp 87-101, ⟨10.4204/EPTCS.185.6⟩. ⟨hal-01176715⟩



Record views


Files downloads