Rewriting Modulo β in the λΠ-Calculus Modulo

Ronan Saillard
(MINES ParisTech, PSL Research University, France)

The lambda-Pi-calculus Modulo is a variant of the lambda-calculus with dependent types where beta-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 lambda-Pi-calculus Modulo. However, they hold if the rewrite system generated by the rewrite rules together with beta-reduction is confluent. But this is too restrictive. To handle the case where non confluence comes from the interference between the beta-reduction and rewrite rules with lambda-abstraction on their left-hand side, we introduce a notion of rewriting modulo beta for the lambda-Pi-calculus Modulo. We prove that confluence of rewriting modulo beta is enough to ensure subject reduction and uniqueness of types. We achieve our goal by encoding the lambda-Pi-calculus Modulo into Higher-Order Rewrite System (HRS). As a consequence, we also make the confluence results for HRSs available for the lambda-Pi-calculus Modulo.

In Iliano Cervesato and Kaustuv Chaudhuri: Proceedings Tenth International Workshop on Logical Frameworks and Meta Languages: Theory and Practice (LFMTP 2015), Berlin, Germany, 1 August 2015, Electronic Proceedings in Theoretical Computer Science 185, pp. 87–101.
Published: 27th July 2015.

ArXived at: http://dx.doi.org/10.4204/EPTCS.185.6 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org