Seventeenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2002)

Paper: Games on Graphs and Sequentially Realizable Functionals (at LICS 2002)

Authors: Martin Hyland Andrea Schalk


We present a new category of games on graphs as a model for Intuitionistic Linear Logic. The model has the computational flavour of concrete data structures but embeds fully and faithfully in an abstract games model. The resulting model for PCF differs markedly from the sequential algorithms model. However we show that the extensional collapse consists of the sequentially realizable functionals. This provides support for the Longley Conjecture.


    author = 	 {Martin Hyland and Andrea Schalk},
    title = 	 {Games on Graphs and Sequentially Realizable Functionals},
    booktitle =  {Proceedings of the Seventeenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2002},
    year =	 2002,
    editor =	 {Gordon Plotkin},
    month =	 {July}, 
    location =   {Copenhagen, Denmark}, 
    publisher =	 {IEEE Computer Society Press}