Paper: Full Abstraction and Universality via Realisability (at LICS 1999)

Authors: Michael Marz Alexander Rohr Thomas Streicher

Abstract

We construct fully abstract realisability models of PCF. In particular, we prove a variant of the Longley-Phoa Conjecture by showing that the realisability model over an untyped lambda-calculus with arithmetic is fully abstract for PCF. Further we consider the extension of our results to a general sequential functional programming language SFPL giving rise to universal realisability models for SFPL.

BibTeX

  @InProceedings{MarzRohrStreicher-FullAbstractionandU,
    author = 	 {Michael Marz and Alexander Rohr and Thomas Streicher},
    title = 	 {Full Abstraction and Universality via Realisability},
    booktitle =  {Proceedings of the Fourteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1999)},
    year =	 {1999},
    month =	 {July}, 
    pages =      {174--182},
    location =   {Trento, Italy}, 
    publisher =	 {IEEE Computer Society Press}
  }