On Equivalence and Canonical Forms in the LF Type Theory

Details On Equivalence and Canonical Forms in the LF Type Theory On Equivalence and Canonical Forms in the LF Type Theory

2001-10-11

arxiv.org/abs/cs/0110028v1

Computer Science

Logic in Computer Science

41 pages

Scientific paper

Decidability of definitional equality and conversion of terms into canonical form play a central role in the meta-theory of a type-theoretic logical framework. Most studies of definitional equality are based on a confluent, strongly-normalizing notion of reduction. Coquand has considered a different approach, directly proving the correctness of a practical equivalance algorithm based on the shape of terms. Neither approach appears to scale well to richer languages with unit types or subtyping, and neither directly addresses the problem of conversion to canonical. In this paper we present a new, type-directed equivalence algorithm for the LF type theory that overcomes the weaknesses of previous approaches. The algorithm is practical, scales to richer languages, and yields a new notion of canonical form sufficient for adequate encodings of logical systems. The algorithm is proved complete by a Kripke-style logical relations argument similar to that suggested by Coquand. Crucially, both the algorithm itself and the logical relations rely only on the shapes of types, ignoring dependencies on terms.

Affiliated with

Also associated with

No associations

Rating

On Equivalence and Canonical Forms in the LF 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 Equivalence and Canonical Forms in the LF Type Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Equivalence and Canonical Forms in the LF Type Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-716363