Definitions by Rewriting in the Calculus of Constructions

Preprint

11 October 2006

preprint
Published by arXiv in arXiv

https://doi.org/10.48550/arXiv.cs/0610065

Abstract

The main novelty of this paper is to consider an extension of the Calculus of Constructions where predicates can be defined with a general form of rewrite rules. We prove the strong normalization of the reduction relation generated by the beta-rule and the user-defined rules under some general syntactic conditions including confluence. As examples, we show that two important systems satisfy these conditions: a sub-system of the Calculus of Inductive Constructions which is the basis of the proof assistant Coq, and the Natural Deduction Modulo a large class of equational theories.

Keywords

CALCULUS OF CONSTRUCTIONS
STRONG NORMALIZATION
INCLUDING CONFLUENCE
GENERAL SYNTACTIC
DEDUCTION MODULO
SYSTEMS SATISFY
CONSTRUCTIONS
MAIN NOVELTY
REWRITE

All Related Versions

Version 1, 2006-10-11, ArXiv

This publication has 0 references indexed in Scilit: