Paper: Head normal form bisimulation for pairs and the lambda-mu calculus (at LICS 2006)

Authors: Soren B. Lassen

Abstract

Bohm tree equivalence up to possibly infinite \eta expansion for the pure \lambda-calculus can be characterized as a bisimulation equivalence. We call this co-inductive syntactic theory extensional head normal form bisimilarity and in this paper we extend it to the \lambdaFP-calculus (the \lamda-calculus with functional and surjective pairing) and to two untyped variants of Parigot’s \lambda\mu-calculus. We relate the extensional head normal form bisimulation theories for the different calculi via Fujita’s extensional CPS transform into the \lambdaFPcalculus. We prove that extensional hnf bisimilarity is fully abstract for the pure \lambda-calculus by a co-inductive reformulation of Barendregt’s proof for Bohm tree equivalence up to possibly infinite \eta expansion. The proof uses the so-called Bohm-out technique from Bohm’s proof of the Separation Property for the \lambda-calculus. Moreover, we extend the full abstraction result to extensional hnf bisimilarity for the \lambdaFP-calculus. For the "standard" \lambda\mu-calculus, the Separation Property fails, as shown by David and Py, and for the same reason extensional hnf bisimilarity is not fully abstract. However, an "extended" variant of the \lambda\mu-calculus satisfies the Separation Property, as shown by Saurin, and we show that extensional hnf bisimilarity is fully abstract for this extended \lambda\mu-calculus.

BibTeX

  @InProceedings{Lassen-Headnormalformbisim,
    author = 	 {Soren B. Lassen},
    title = 	 {Head normal form bisimulation for pairs and the lambda-mu calculus},
    booktitle =  {Proceedings of the Twenty-First Annual IEEE Symposium on Logic in Computer Science (LICS 2006)},
    year =	 {2006},
    month =	 {August}, 
    pages =      {297--306},
    location =   {Seattle, Washington, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }