On Irrelevance and Algorithmic Equality in Predicative Type Theory

Details On Irrelevance and Algorithmic Equality in Predicative Type Theory On Irrelevance and Algorithmic Equality in Predicative Type Theory

2012-03-21

arxiv.org/abs/1203.4716v2

LMCS 8 (1:29) 2012

Computer Science

Logic in Computer Science

36 pages, superseds the FoSSaCS 2011 paper of the first author, titled "Irrelevance in Type Theory with a Heterogeneous Equali

Scientific paper

10.2168/LMCS-8(1:29)2012

Dependently typed programs contain an excessive amount of static terms which are necessary to please the type checker but irrelevant for computation. To separate static and dynamic code, several static analyses and type systems have been put forward. We consider Pfenning's type theory with irrelevant quantification which is compatible with a type-based notion of equality that respects eta-laws. We extend Pfenning's theory to universes and large eliminations and develop its meta-theory. Subject reduction, normalization and consistency are obtained by a Kripke model over the typed equality judgement. Finally, a type-directed equality algorithm is described whose completeness is proven by a second Kripke model.

Affiliated with

Also associated with

No associations

Rating

On Irrelevance and Algorithmic Equality in Predicative Type Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Irrelevance and Algorithmic Equality in Predicative Type Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Irrelevance and Algorithmic Equality in Predicative Type Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-488599