Categories of Coalgebraic Games with Selective Sum

• Autorzy: Honsell F. , Lenisa M. , Pellarini D.

Identyfikatory

DOI

10.3233/FI-2014-1107

• Języki publikacji: EN

Abstrakty

EN

Joyal’s categorical construction on (well-founded) Conway games and winning strategies provides a compact closed category, where tensor and linear implication are defined via Conway disjunctive sum (in combination with negation for linear implication). The equivalence induced on games by the morphisms coincides with the contextual closure of the equideterminacy relation w.r.t. the disjunctive sum. Recently, the above categorical construction has been generalized to non-wellfounded games. Here we investigate Joyal’s construction for a different notion of sum, i.e. selective sum. While disjunctive sum reflects the interleaving semantics, selective sum accommodates a form of parallelism, by allowing the current player to move in different parts of the board simultaneously. We show that Joyal’s categorical construction can be successfully extended to selective sum, when we consider alternating games, i.e. games where each position is marked as Left player (L) or Right player (R), that is only L or R can move from that position, R starts, and L/R positions strictly alternate. Alternating games typically arise in the context of Game Semantics. This category of well-founded games with selective sum is symmetric monoidal closed, and it induces exactly the equideterminacy relation. Generalizations to non-wellfounded games give linear categories, i.e. models of Linear Logic. Our game models, providing a certain level of parallelism, may be situated halfway between traditional sequential alternating gamemodels and the concurrent game models by Abramsky and Mellies. We work in a context of coalgebraic games, whereby games are viewed as elements of a final coalgebra, and game operations are defined as final morphisms.

Słowa kluczowe

EN

games; strategies; Conway Games; coalgebras; categories of games and strategies

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 134, nr 3/4
• Strony: 395--414
• Opis fizyczny: Bibliogr. 28 poz.

Twórcy

autor

Honsell F.

• Dipartimento di Matematica e Informatica, Università di Udine, Italy

autor

Lenisa M.

• Dipartimento di Matematica e Informatica, Università di Udine, Italy

autor

Pellarini D.

• Dipartimento di Matematica e Informatica, Università di Udine, Italy

Bibliografia

• [1] S. Abramsky. Semantics of Interaction: an introduction to Game Semantics, CLiCS’96 School, P. Dybjer et al., eds., Cambridge University Press, 1997.
• [2] S. Abramsky, R. Jagadesaan. Games and Full Completeness for Multiplicative Linear logic, Journal of Symbolic Logic 59, 1994, 543–574.
• [3] S. Abramsky, R. Jagadeesan, P.Malacaria. Full abstraction for PCF, Information and Computation 163, 2000, 404–470.
• [4] S. Abramsky, P.A. Mellies. Concurrent games and full completeness, LICS’99, IEEE Computer Science Press, 1999, 431–444.
• [5] P. Aczel. Non-wellfounded sets, CSLI Lecture Notes 14, Stanford 1988.
• [6] J. Barwise, L. Moss. Vicious Circles, CSLI Lecture Notes 60, Stanford 1996.
• [7] J. van Benthem. Extensive games as process models, Journal of Logic, Language and Information 11, 2002.
• [8] E. Berlekamp, J. Conway, R. Guy.WinningWays, Academic Press, 1982.
• [9] G. Bierman. What is a categorical Model of Intuitionistic Linear Logic? TLCA’95, Springer LNCS 902, 1995, 78–93.
• [10] D. Cancila, F. Honsell, M. Lenisa. Generalized Coiteration Schemata, CMCS’03, ENTCS 82(1), 2003.
• [11] P. Clairambault, J. Gutierrez, G. Winskel. The winning ways of concurrent games, LICS 2012, IEEE Computer Science Press, 2012.
• [12] J.H. Conway. On Numbers and Games, A K Peters Ltd, 2001.
• [13] M. Forti, F. Honsell. Set-theory with free construction principles, Ann. Scuola Norm. Sup. Pisa, Cl. Sci. (4)10, 1983, 493–522.
• [14] F. Honsell, M. Lenisa. Conway Games, algebraically and coalgebraically, Logical Methods in Computer Science 7(3), 2011.
• [15] F. Honsell, M. Lenisa, R. Redamalla. Equivalences and Congruences on Infinite Conway Games, RAIRO Theoretical Informatics and Applications 46(2), 2012, 231–259.
• [16] F. Honsell, M. Lenisa, R. Redamalla. Categories of Coalgebraic Games, MFCS 2012, Springer LNCS 7464, 2012, 503–515.
• [17] M. Hyland, L. Ong. Fair Games and Full Completeness for Multiplicative Linear Logic without the MIX-Rule, Technical Report, available at ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Luke.Ong/fcomplete.ps.gz .
• [18] M. Hyland, L. Ong. On Full Abstraction for PCF: I, II, and III, Information and Computation 163, 2000, 285–408.
• [19] M. Hyland, A. Schalk. Games on Graphs and Sequentially Realizable Functionals, LICS’02, IEEE Computer Science Press, 2002, 257–264.
• [20] B. Jacobs, J. Rutten. A tutorial on (co)algebras and (co)induction, Bulletin of the EATCS 62, 1996, 222–259.
• [21] A. Joyal. Remarques sur la Theorie des Jeux a deux personnes, Gazette des sciences mathematiques du Quebec 1(4), 1977.
• [22] P.A.Mellies. Comparing hierarchies of types in models of linear logic, Information and Computation 189(2), 2004, 202–234.
• [23] P.A. Mellies. Asynchronous games 3: an innocent model of linear logic, CTCS2004, ENTCS 122, 2005.
• [24] P.A. Mellies. Asynchronous games 2: the true concurrency of innocence, Theoretical Computer Science 358(2-3), 2006.
• [25] P.A. Mellies. Categorical semantics of linear logic, Panoramas et Synthéses 27, Société Mathématique de France, 2009.
• [26] P.A. Mellies, N. Tabareau, C. Tasson. An explicit formula for the free exponential modality of linear logic, ICALP’09, Springer LNCS 555, 2009.
• [27] M. Pauly, From Programs to Games: Invariance and Safety for Bisimulation, CSL’09, Springer LNCS 5771, 485–496.
• [28] S. Rideau, G. Winskel. Concurrent Strategies, LICS 2011, IEEE Computer Science Press, 2011.