Games on graphs and sequentially realizable functionals. Extended abstract
Proceedings - Symposium on Logic in Computer Science - Trang 257-264
Tóm tắt
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.
Từ khóa
#Logic #Concrete #Computer science #Data structures #Mathematical model #Embedded computing #Algorithm design and analysis #Tree graphsTài liệu tham khảo
10.1016/S0168-0072(01)00110-5
melliés, 0, On the extensional content of sequential games, available electronically at
van oosten, 1997, A combinatory algebra for sequential functionals of finite type, Technical Report 996
winskel, 1986, Event structures, Petri Nets Applications and Relationships to Other Models of Concurrency Advances in Petri Nets 1986, 255, 325, 10.1007/3-540-17906-2_31
10.1007/3-540-58027-1_2
10.1007/978-1-4612-0317-9
10.1006/inco.1998.2781
10.1017/S0960129500000281
hyland, 2002, Glueing and orthogonality for models of linear logic, Theoretical Computer Science
hyland, 1999, Abstract games for linear logic. extended abstract, Proceedings of CTCS '99 Conference on Category Theory and Computer Science volume 29 of Electronic Notes on Theoretical Computer Science
10.1016/S0304-3975(82)80002-9
10.1109/LICS.1997.614933
10.1016/0304-3975(93)90090-G