Distributed Strategies Made Easy

Authors Simon Castellan, Pierre Clairambault, Glynn Winskel



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.81.pdf
  • Filesize: 488 kB
  • 13 pages

Document Identifiers

Author Details

Simon Castellan
Pierre Clairambault
Glynn Winskel

Cite AsGet BibTex

Simon Castellan, Pierre Clairambault, and Glynn Winskel. Distributed Strategies Made Easy. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.81

Abstract

Distributed/concurrent strategies have been introduced as special maps of event structures. As such they factor through their "rigid images," themselves strategies. By concentrating on such "rigid image" strategies we are able to give an elementary account of distributed strategies and their composition, resulting in a category of games and strategies. This is in contrast to the usual development where composition involves the pullback of event structures explicitly and results in a bicategory. It is shown how, in this simpler setting, to extend strategies to probabilistic strategies; and indicated how through probability we can track nondeterministic branching behaviour, that one might otherwise think lost irrevocably in restricting attention to "rigid image" strategies.
Keywords
  • Games
  • Strategies
  • Event Structures
  • Probability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Samson Abramsky and Paul-André Melliès. Concurrent games and full completeness. In LICS '99. IEEE Computer Society, 1999. Google Scholar
  2. Simon Castellan and Pierre Clairambault. Causality vs interleavings in concurrent games semantics. In CONCUR'16, 2016. Google Scholar
  3. Simon Castellan, Jonathan Hayman, Marc Lasson, and Glynn Winskel. Strategies as concurrent processes. ENTCS, 308, 2014. Google Scholar
  4. Gian Luca Cattani and Glynn Winskel. Profunctors, open maps and bisimulation. Mathematical Structures in Computer Science, 15(3):553-614, 2005. Google Scholar
  5. Pierre Clairambault, Julian Gutierrez, and Glynn Winskel. The winning ways of concurrent games. In LICS 2012: 235-244, 2012. Google Scholar
  6. Pierre Clairambault and Glynn Winskel. On concurrent games with payoff. Electr. Notes Theor. Comput. Sci. 298: 71-92, 2013. Google Scholar
  7. John Conway. On Numbers and Games. Wellesley, MA: A K Peters, 2000. Google Scholar
  8. Claudia Faggian and Mauro Piccolo. Partial orders, event structures and linear strategies. In TLCA '09, volume 5608 of LNCS. Springer, 2009. Google Scholar
  9. Tom Hirschowitz and Damien Pous. Innocent strategies as presheaves and interactive equivalences for CCS. Sci. Ann. Comp. Sci., 22(1):147-199, 2012. Google Scholar
  10. Martin Hyland. Some reasons for generalising domain theory. Mathematical Structures in Computer Science, 20(2):239-265, 2010. Google Scholar
  11. Claire Jones and Gordon Plotkin. A probabilistic powerdomain of valuations. In LICS '89. IEEE Computer Society, 1989. Google Scholar
  12. Andre Joyal. Remarques sur la théorie des jeux à deux personnes. Gazette des sciences mathématiques du Québec, 1(4), 1997. Google Scholar
  13. Paul-André Melliès and Samuel Mimram. Asynchronous games: Innocence without alternation. In CONCUR, volume 4703 of LNCS, pages 395-411, 2007. Google Scholar
  14. Silvain Rideau and Glynn Winskel. Concurrent strategies. In LICS 2011. Google Scholar
  15. Peter Selinger and Benoît Valiron. Quantum lambda calculus. In Simon Gay and Ian Mackie, editors, Semantic Techniques in Quantum Computation, chapter 4, pages 135-172. Cambridge University Press, 2009. Google Scholar
  16. Jonathan Hayman Simon Castellan, Pierre Clairambault and Glynn Winskel. Non-angelic concurrent game semantics. 2016. Google Scholar
  17. Takeshi Tsukada and C.-H. Luke Ong. Nondeterminism in game semantics via sheaves. In LICS 2015. IEEE Computer Society, 2015. Google Scholar
  18. Glynn Winskel. Event structure semantics for CCS and related languages. In ICALP'82, LNCS 140, 1982. Google Scholar
  19. Glynn Winskel. Event structures as presheaves -two representation theorems. In CONCUR '99, 1999. Google Scholar
  20. Glynn Winskel. Event structures with symmetry. Electr. Notes Theor. Comput. Sci. 172: 611-652, 2007. Google Scholar
  21. Glynn Winskel. Winning, losing and drawing in concurrent games with perfect or imperfect information. In Festschrift for Dexter Kozen, volume 7230 of LNCS. Springer, 2012. Google Scholar
  22. Glynn Winskel. Distributed probabilistic and quantum strategies. ENTCS 298, 2013. Google Scholar
  23. Glynn Winskel. Strategies as profunctors. In FOSSACS 2013, volume 7794 of LNCS. Springer, 2013. Google Scholar
  24. Glynn Winskel. Probabilistic and quantum event structures. In Festschrift for Prakash Panangaden, volume 8464 of LNCS. Springer, 2014. Google Scholar
  25. Glynn Winskel. ECSYM Notes: Event Structures, Stable Families and Concurrent Games. http://www.cl.cam.ac.uk/∼gw104/ecsym-notes.pdf, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail