17th Annual IEEE Symposium on Logic in Computer Science (LICS'02)
Games on Graphs and Sequentially Realizable Functionals Extended Abstract
Copenhagen, Denmark
July 22-July 25
ISBN: 0-7695-1483-9
We present a new category of games on graphs and derive from it a model for Intuitionistic Linear Logic. Our category has the computational flavour of concrete data structures but embeds fully and faithfully in an abstract games model. It differs markedly from the usual Intuitionistic Linear Logic setting for sequential algorithms. However, we show that with a natural exponential we obtain a model for PCF essentially equivalent to the sequential algorithms model. We briefly consider a more extensional setting and the prospects for a better understanding of the Longley Conjecture.