Arithmetical proofs of strong normalization results for symmetric lambda calculi

Details Arithmetical proofs of strong normalization results for symmetric lambda calculi Arithmetical proofs of strong normalization results for symmetric lambda calculi

2009-05-06

arxiv.org/abs/0905.0762v1

Fundamenta Informaticae 77, 4 (2007) 489-510

Mathematics

Logic

Scientific paper

We give arithmetical proofs of the strong normalization of two symmetric $\lambda$-calculi corresponding to classical logic. The first one is the $\bar{\lambda}\mu\tilde{\mu}$-calculus introduced by Curien & Herbelin. It is derived via the Curry-Howard correspondence from Gentzen's classical sequent calculus LK in order to have a symmetry on one side between "program" and "context" and on other side between "call-by-name" and "call-by-value". The second one is the symmetric $\lambda \mu$-calculus. It is the $\lambda \mu$-calculus introduced by Parigot in which the reduction rule $\mu'$, which is the symmetric of $\mu$, is added. These results were already known but the previous proofs use candidates of reducibility where the interpretation of a type is defined as the fix point of some increasing operator and thus, are highly non arithmetical.

Affiliated with

Also associated with

No associations

Rating

Arithmetical proofs of strong normalization results for symmetric lambda calculi 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 Arithmetical proofs of strong normalization results for symmetric lambda calculi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetical proofs of strong normalization results for symmetric lambda calculi will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-541519