Abstract
Concurrent games as event structures form a partial order model of concurrency where concurrent behaviour is captured by nondeterministic concurrent strategies—a class of maps of event structures. Extended with winning conditions, the model is also able to give semantics to logics of various kinds. An interesting subclass of this game model is the one considering deterministic strategies only, where the induced model of strategies can be fully characterised by closure operators. The model based on closure operators exposes many interesting mathematical properties and allows one to define connections with many other semantic models where closure operators are also used. However, such a closure operator semantics has not been investigated in the more general nondeterministic case. Here we do so, and show that some nondeterministic concurrent strategies can be characterised by a new definition of nondeterministic closure operators which agrees with the standard game model for event structures and with its extension with winning conditions.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abramsky, S.: Sequentiality vs. concurrency in games and logic. Math. Struct. Comput. Sci. 13(4), 531–565 (2003)
Abramsky, S., Jagadeesan, R., Malacaria, P.: Full abstraction for PCF. Inf. Comput. 163(2), 409–470 (2000)
Abramsky, S., Melliès, P.: Concurrent games and full completeness. In: LICS, pp. 431–442. IEEE Computer Society (1999)
Berry, G.: Modèles complètement adéquats et stables des lambda-calculs typés. Ph.D. thesis, University of Paris VII (1979)
Clairambault, P., Gutierrez, J., Winskel, G.: The winning ways of concurrent games. In: LICS, pp. 235–244. IEEE Computer Society (2012)
Desel, J., Esparza, J.: ree Choice Petri Nets, Cambridge Tracts in Theoretical Computer Science, vol. 40. Cambridge University Press, Cambridge (1995)
Gutierrez, J.: Concurrent logic games on partial orders. In: Beklemishev, L.D., de Queiroz, R. (eds.) WoLLIC 2011. LNCS, vol. 6642, pp. 146–160. Springer, Heidelberg (2011)
Harmer, R., Hyland, M., Melliès, P.: Categorical combinatorics for innocent strategies. In: LICS, pp. 379–388. IEEE Computer Society (2007)
Hyland, J.M.E., Ong, C.L.: On full abstraction for PCF: I, II, and III. Inf. Comput. 163(2), 285–408 (2000)
Kahn, G., Plotkin, G.: Concrete domains. Technical report, INRIA (1993)
Melliès, P.-A., Mimram, S.: Asynchronous games: innocence without alternation. In: Caires, L., Vasconcelos, V.T. (eds.) CONCUR 2007. LNCS, vol. 4703, pp. 395–411. Springer, Heidelberg (2007)
Nielsen, M., Palamidessi, C., Valencia, F.D.: Temporal concurrent constraint programming: Denotation, logic and applications. Nord. J. Comput. 9(1), 145–188 (2002)
Nielsen, M., Winskel, G.: Models for concurrency. In: Handbook of Logic in Computer Science, pp. 1–148. Oxford University Press (1995)
Olarte, C., Valencia, F.D.: Universal concurrent constraint programing: symbolic semantics and applications to security. In: SAC, pp. 145–150. ACM (2008)
Plotkin, G.D.: A powerdomain construction. SIAM J. Comput. 5(3), 452–487 (1976)
Rideau, S., Winskel, G.: Concurrent strategies. In: LICS, pp. 409–418. IEEE Computer Society (2011)
Saraswat, V.A., Rinard, M.C., Panangaden, P.: Semantic foundations of concurrent constraint programming. In: POPL, pp. 333–352. ACM Press (1991)
Saunders-Evans, L., Winskel, G.: Event structure spans for nondeterministic dataflow. Electron. Notes Theoret. Comput. Sci. 175(3), 109–129 (2007)
Winskel, G.: Deterministic concurrent strategies. Formal Aspects Comput. 24(4–6), 647–660 (2012)
Winskel, G.: Strategies as profunctors. In: Pfenning, F. (ed.) FOSSACS 2013 (ETAPS 2013). LNCS, vol. 7794, pp. 418–433. Springer, Heidelberg (2013)
Acknowledgment
I thank Paul Harrenstein, Glynn Winskel, and Michael Wooldridge for their comments and support. Also, I acknowledge with gratitude the support of the ERC Advanced Research Grant 291528 (“RACE”) at Oxford.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Gutierrez, J. (2015). A Mathematical Game Semantics of Concurrency and Nondeterminism. In: Leucker, M., Rueda, C., Valencia, F. (eds) Theoretical Aspects of Computing - ICTAC 2015. ICTAC 2015. Lecture Notes in Computer Science(), vol 9399. Springer, Cham. https://doi.org/10.1007/978-3-319-25150-9_35
Download citation
DOI: https://doi.org/10.1007/978-3-319-25150-9_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25149-3
Online ISBN: 978-3-319-25150-9
eBook Packages: Computer ScienceComputer Science (R0)