Classical Proofs, Typed Processes, and Intersection Types Extended Abstract

Abstract

Curien and Herbelin provided a Curry and Howard correspondence between classical prepositional logic and a computational model called λ̄μμμ which is a calculus for interpreting classical sequents. A new terminology for λ̄μμ̄ in terms of pairs of callers-callees which we name capsules enlightens a natural link between λ̄μμ̄ and process calculi. In this paper we propose an intersection type system λ̄μμ̄ which is an extension of λ̄μμ̄ with intersection types. We prove that all strongly normalizing λ̄μμ̄-terms are typeable in the new system, which was not the case in λ̄μμ̃. Also, we prove that all typeable μ̃-free terms are strongly normalizing. © Springer-Verlag 2004.