Source author record

Matthieu Sozeau

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Programming Languages Logic in Computer Science

Catalog footprint

Research overview

2works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Consistency of the Predicative Calculus of Cumulative Inductive Constructions (pCuIC)

In order to avoid well-know paradoxes associated with self-referential definitions, higher-order dependent type theories stratify the theory using a countably infinite hierarchy of universes (also known as sorts), Type $_0$ : Type $_1$ : $\cdots$ . Such type systems are called cumulative if for any type $A$ we have that $A$ : Type $_{i}$ implies $A$ : Type $_{i+1}$ . The predicative calculus of inductive constructions (pCIC) which forms the basis of the Coq proof assistant, is one such system. In this paper we present and establish the soundness of the predicative calculus of cumulative inductive constructions (pCuIC) which extends the cumulativity relation to inductive types.

preprint2015arXiv

Equations for Hereditary Substitution in Leivant's Predicative System F: A Case Study

This paper presents a case study of formalizing a normalization proof for Leivant's Predicative System F using the Equations package. Leivant's Predicative System F is a stratified version of System F, where type quantification is annotated with kinds representing universe levels. A weaker variant of this system was studied by Stump & Eades, employing the hereditary substitution method to show normalization. We improve on this result by showing normalization for Leivant's original system using hereditary substitutions and a novel multiset ordering on types. Our development is done in the Coq proof assistant using the Equations package, which provides an interface to define dependently-typed programs with well-founded recursion and full dependent pattern- matching. Equations allows us to define explicitly the hereditary substitution function, clarifying its algorithmic behavior in presence of term and type substitutions. From this definition, consistency can easily be derived. The algorithmic nature of our development is crucial to reflect languages with type quantification, enlarging the class of languages on which reflection methods can be used in the proof assistant.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.