Games on Graphs and Sequentially Realizable Functionals

Martin Hyland, Andrea Schalk

To appear at Symposium on Logic in Computer Science (LICS'2002), Copenhagen, Denmark, July 22nd - 25th, 2002


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.

Server START Conference Manager
Update Time 15 Mar 2002 at 15:30:30
Start Conference Manager
Conference Systems