Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2017, Vol. 11 Issue (6) : 948-970    https://doi.org/10.1007/s11704-016-6155-5
TUTORIAL
Using coalgebras and the Giry monad for interpreting game logics— a tutorial
Ernst-Erich DOBERKAT()
Math++ Software, Bochum 44879, Germany
 Download: PDF(441 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

The stochastic interpretation of Parikh’s game logic should not follow the usual pattern of Kripke models, which in turn are based on the Kleisli morphisms for the Giry monad, rather, a specific and more general approach to probabilistic nondeterminism is required.We outline this approach together with its probabilistic and measure theoretic basis, introducing in a leisurely pace the Giry monad and its Kleisli morphisms together with important techniques for manipulating them. Proof establishing specific techniques are given, and pointers to the extant literature are provided.

After working through this tutorial, the reader should find it easier to follow the original literature in this and related areas, and it should be possible for her or him to appreciate measure theoretic arguments for original work in the areas of Markov transition systems, and stochastic effectivity functions.

Keywords coalgebras      modal logics      monads      Giry monad      upper closed monad      composition of monads      game logics     
Corresponding Author(s): Ernst-Erich DOBERKAT   
Just Accepted Date: 05 July 2016   Online First Date: 17 October 2016    Issue Date: 07 December 2017
 Cite this article:   
Ernst-Erich DOBERKAT. Using coalgebras and the Giry monad for interpreting game logics— a tutorial[J]. Front. Comput. Sci., 2017, 11(6): 948-970.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-6155-5
https://academic.hep.com.cn/fcs/EN/Y2017/V11/I6/948
1 RuttenJ J M M. Universal coalgebra: a theory of systems. Theoretical Computer Science, 2000, 249(1): 3–80
https://doi.org/10.1016/S0304-3975(00)00056-6
2 VenemaY. 6 Algebras and co-algebras. Studies in Logic and Practical Reasoning, 2007, 3: 331–426
https://doi.org/10.1016/S1570-2464(07)80009-7
3 JacobsB. Introduction to Coalgebra: Towards Mathematics of States and Observations. Cambridge: Cambridge University Press, 2016
4 DoberkatE E. Special Topics in Mathematics for Computer Science: Sets, Categories, Topologies, Measures. Springer, 2015
https://doi.org/10.1007/978-3-319-22750-4
5 DoberkatE E. Algebraic properties of stochastic effectivity functions. Journal of Logical and Algebraic Methods in Programming, 2014, 83(3): 339–358
https://doi.org/10.1016/j.jlamp.2014.03.002
6 DoberkatE E. A stochastic interpretation of game logic. 2016, arXiv: 1403.7765
7 HennessyM, MilnerR. On observing nondeterminism and concurrency. In: Proceedings of the International Colloquium on Automata, Languages, and Programming. 1980, 299–309
https://doi.org/10.1007/3-540-10003-2_79
8 DoberkatE E. A note on the coalgebraic interpretation of game logic. Rend.istit.mat.univ.trieste, 2010, 42: 191–203
9 DoberkatE E. Stochastic Coalgebraic Logic. Berlin: Springer-Verlag, 2009
https://doi.org/10.1007/978-3-642-02995-0
10 SrivastavaS M. A Course on Borel Sets (Graduate Texts in Mathematics). New York: Springer-Verlag, 1998
https://doi.org/10.1007/978-3-642-85473-6
11 TerrafP S. Unprovability of the logical characterization of bisimulation. Information and Computation, 2011, 209(7): 1048–1056
https://doi.org/10.1016/j.ic.2011.02.003
12 DesharnaisJ, EdalatA, PanangadenP . Bisimulation of labelled Markov processes. Information and Computation, 2002, 179(2): 163–193
https://doi.org/10.1006/inco.2001.2962
13 EdalatA. Semi-pullbacks and bisimulations in categories of Markov processes. Mathematical Structures in Computer Science, 1999, 9(5): 523–543
https://doi.org/10.1017/S0960129599002819
14 DoberkatE E. Semi-pullbacks for stochastic relations over analytic spaces. Mathematical Structures in Computer Science, 2005, 15(4): 647–670
https://doi.org/10.1017/S096012950500472X
15 DoberkatE E. Semi-pullbacks and bisimulations in categories of stochastic relations. In: Proceedings of the International Colloquium on Automata, Languages, and Programming. 2003, 996–1007
https://doi.org/10.1007/3-540-45061-0_77
16 ParikhR.The logic of games and its applications. North-Holland Mathematics Studies, 1985, 102: 111–139
https://doi.org/10.1016/S0304-0208(08)73078-0
17 PaulyM, ParikhR. Game logic—an overview. Studia Logica, 2003, 75(2): 165–182
https://doi.org/10.1023/A:1027354826364
18 Van BenthemJ. Logic games are complete for game logics. Studia Logica, 2003, 75(2): 183–203
https://doi.org/10.1023/A:1027306910434
19 PaulyM. Game Logic for Game Theorists.Centrum voor Wiskunde en Informatica, 2000
20 GoldblattR. Deduction systems for coalgebras over measurable spaces. Journal of Logic and Computation, 2010, 20(5): 1069–1100
https://doi.org/10.1093/logcom/exn092
21 MossL S. Coalgebraic logic. Annals of Pure and Applied Logic, 1999, 96(1): 277–317
https://doi.org/10.1016/S0168-0072(98)00042-6
22 SchröderL. Expressivity of coalgebraic modal logic: the limits and beyond. Theoretical Computer Science, 2008, 390(2): 230–247
https://doi.org/10.1016/j.tcs.2007.09.023
23 D’argenioP R, Terraf P S, WolovickN . Bisimulations for nondeterministic labelled Markov processes. Mathematical Structures in Computer Science, 2012, 22(1): 43–68
https://doi.org/10.1017/S0960129511000454
24 DoberkatE E, TerrafP S. Stochastic non-determinism and effectivity functions. Journal of Logic and Computation, doi: 10.1093/logcom/ exv049 (arxiv: 1405.7141), 2015
25 JechT. Set Theory. 3rd ed. Berlin: Springer-Verlag, 2006
26 HalmosP R. Measure Theory (Graduate Texts in Mathematics). Springer Science & Business Media, 2007
[1] FCS-0948-16155-EED_suppl_1 Download
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed