Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-12-01T08:55:26.406Z Has data issue: false hasContentIssue false
  • English
  • Français

Games and full completeness for multiplicative linear logic

Published online by Cambridge University Press:  12 March 2014

Samson Abramsky  and
Radha Jagadeesan
Samson Abramsky
Affiliation:
Department of Computing, Imperial College of Science, Technology and Medicine, London, SW7 2BZ, England, E-mail: [email protected]
Radha Jagadeesan
Affiliation:
Department of Mathematical Sciences, Loyola University, Chicago, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We present a game semantics for Linear Logic, in which formulas denote games and proofs denote winning strategies. We show that our semantics yields a categorical model of Linear Logic and prove full completeness for Multiplicative Linear Logic with the MIX rule: every winning strategy is the denotation of a unique cut-free proof net. A key role is played by the notion of history-free strategy; strong connections are made between history-free strategies and the Geometry of Interaction. Our semantics incorporates a natural notion of polarity, leading to a refined treatment of the additives. We make comparisons with related work by Joyal, Blass, et al.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 59 , Issue 2 , June 1994 , pp. 543 - 574
Copyright
Copyright © Association for Symbolic Logic 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[Abr91] Abramsky, S., Proofs as processes, unpublished lecture, 1991.Google Scholar
[Abr93] Abramsky, S., Computational interpretations of linear logic, Theoretical Computer Science, vol. 111 (1993), pp. 3–57, revised version of Imperial College Technical Report DoC 90/20, October 1990.CrossRefGoogle Scholar
[AJ92a] Abramsky, S. and Jagadeesan, R., Games and full completeness for multiplicative linear logic, Technical Report DoC 92/24, Imperial College Department of Computing, 10 1992.Google Scholar
[AJ92b] Abramsky, S., New foundations for the geometry of interaction, Proceedings of the seventh symposium on logic in computer science, Computer Society Press of the IEEE, New York, 06 1992, pp. 211–222.Google Scholar
[AJ92c] Abramsky, S., A strong completeness theorem for multiplicative linear logic: Preliminary announcement, E-mail communication on types mailing list, 1992.Google Scholar
[AV93] Abramsky, S. and Vickers, S., Quantales, observational logic and process semantics, Mathematical Structures in Computer Science, vol. 3 (1993), pp. 161–227, revised version of Imperial College Technical Report DoC 90/1, January 1990.CrossRefGoogle Scholar
[Bar79] Barr, M., *-autonomous categories, Lecture Notes in Mathematics, vol. 752, Springer-Verlag, Berlin and New York, 1979.CrossRefGoogle Scholar
[Bar91] Barr, M., *-autonomous categories and linear logic, Mathematical Structures in Computer Science, vol. 1 (1991), pp. 159–178.Google Scholar
[BC85] Berry, G. and Curien, P.-L., Theory and practice of sequential algorithms: the kernel of the applicative language CDS, Algebraic semantics (Reynolds, J. C. and Nivat, M., editors), Cambridge University Press, London and New York, 1985, pp. 35–84.Google Scholar
[BFSS90] Bainbridge, S., Freyd, P. J., Scedrov, A., and Scott, P., Functorial polymorphism, Theoretical Computer Science, vol. 70 (1990), pp. 35–64.CrossRefGoogle Scholar
[Bla72] Blass, A., Degrees of indeterminacy of games, Fundamenta Mathematicae, vol. LXXVII (1972), pp. 151–162.Google Scholar
[Bla92a] Blass, A., personal communication (1992).Google Scholar
[Bla92b] Blass, A., A game semantics for linear logic, Annals of Pure and Applied Logic, vol. 56 (1992), pp. 183–220.CrossRefGoogle Scholar
[Blu92] Blute, R., Linear logic, coherence, and dinaturality, technical report, McGill University, Quebec, 1992.Google Scholar
[CGW87] Coquand, T., Gunter, C., and Winskel, G., dI-domains as a model of polymorphism, Third workshop on the mathematical foundations of programming language semantics, Springer-Verlag, New York, 1987, pp. 344–363.Google Scholar
[Con76] Conway, J. H., On numbers and games, volume 6 of London Mathematical Society Monographs, vol. 6, Academic Press, New York, 1976.Google Scholar
[Cur92] Curien, P. L., Concrete data structures, sequential algorithms and linear logic, e-mail communication on types mailing list, (1992).Google Scholar
[dP89] de Paiva, V. C. V., The dialectica categories, Categories in Computer Science and Logic (Gray, J. W. and Scedrov, A., editors), Contemporary Mathematics, vol. 92, American Mathematical Society, Providence, Rhode Island, 1989, pp. 47–62.Google Scholar
[DP90] Davey, B. A. and Priestley, H. A., Introduction to lattices and order, Cambridge University Press, London and New York, 1990.Google Scholar
[DR89] Danos, V. and Regnier, L., The structure of multiplicatives, Archive for Mathematical Logic, vol. 28 (1989), pp. 181–203.Google Scholar
[FR90] Fleury, A. and Retoré, C., The MIX rule, unpublished note, 1990.Google Scholar
[FS91] Freyd, P. J. and Scedrov, A., Categories, allegories, North-Holland Mathematical Library, vol 39, Elsevier Science Publishers, Amsterdam, 1990.Google Scholar
[GAL92] Gonthier, G, Abadi, M., and Levy, J. J., Linear logic without boxes, Proceedings of the seventh symposium on logic in computer science, Computer Society Press of the IEEE, New York, 1992, pp. 223–234.Google Scholar
[Gir86] Girard, J.-Y., The system F of variable types, fifteen years later, Theoretical Computer Science, vol. 45 (1986), pp. 159–192.CrossRefGoogle Scholar
[Gir87] Girard, J.-Y., Linear logic, Theoretical Computer Science, vol. 50 (1987), pp. 1–102.Google Scholar
[Gir88] Girard, J.-Y., Geometry of interaction 2: deadlock-free algorithms, International Conference on Computer Logic, COLOG 88 (Martin-Löf, P. and Mints, G., editors), Lecture Notes in Computer Science, vol. 417, Springer-Verlag Berlin and New York, 1988, pp. 76–93.Google Scholar
[Gir89a] Girard, J.-Y., Geometry of interaction 1: interpretation of system F, Logic Colloquium 88 (Ferro, R. et al, editors), North-Holland, Amsterdam, 1989, pp. 221–260.Google Scholar
[Gir89b] Girard, J.-Y., Towards a geometry of interaction, Categories in computer science and logic (Gray, J. W. and Scedrov, A., editors), Contemporary Mathematics, vol. 92, American Mathematical Society, Providence, Rhode Island, 1989, pp. 69–108.Google Scholar
[Gir91a] Girard, J.-Y., A new constructive logic: classical logic, Mathematical Structures in Computer Science, vol. 1 (1991), pp. 255–296.CrossRefGoogle Scholar
[Gir91b] Girard, J.-Y., On the unity of logic, submitted.Google Scholar
[Hoa85] Hoare, C. A. R., Communicating sequential processes, Prentice Hall, Englewood Cliffs, New Jersey, 1985.Google Scholar
[HRR89] Hyland, J. M. E., Robinson, E. P., and Rosolini, G., Algebraic types in per models, Fifth conference on mathematical foundations in programming semantics, Lecture Notes in Computer Science, vol. 442, Springer-Verlag, Berlin and New York, 1989, pp. 333–350.CrossRefGoogle Scholar
[Hy190] Hyland, J. M. E., Conway games and linear logic, unpublished lecture (1990).Google Scholar
[Jac92] Jacobs, B., Semantics of weakening and contraction, 1992, preprint.Google Scholar
[Joy77] Joyal, A., Remarques sur la theorie des jeux a deux personnes, Gazette des sciences mathematiques du Quebec, vol. 1 (1977).Google Scholar
[Laf90] Lafont, Y., Interaction nets, Proceedings of the seventeenth ACM symposium on principles of programming languages, 1990, pp. 95–108.Google Scholar
[Lam92] Lamarche, F., Sequential algorithms, games and linear logic, unpublished lecture, 1992.Google Scholar
[LS91] Lafont, Y. and Streicher, T., Games semantics for linear logic, Proceedings of the sixth annual symposium on logic in computer science, Computer Society Press, Rockville, Maryland, 1991, pp. 43–51.Google Scholar
[Mil75] Milner, R., Processes, a mathematical model of computing agents, Logic colloquium, Bristol 1973, North-Holland, Amsterdam, 1975, pp. 157–174.Google Scholar
[Plo77] Plotkin, G. D., LCF considered as a programming language, Theoretical Computer Science, vol. 5 (1977), pp. 223–255.Google Scholar
[See89] Seeley, R., *-autonomous categories, cofree coalgebras and linear logic, Categories in Computer Science and Logic, (Gray, J. W. and Scedrov, A., editor), Contemporary Mathematics, vol. 92, American Mathematical Society, Providence, Rhode Island, 1989, pp. 371–382.CrossRefGoogle Scholar