The compositional construction of Markov processes II
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 45 (2011) no. 1, p. 117-142

We add sequential operations to the categorical algebra of weighted and Markov automata introduced in [L. de Francesco Albasini, N. Sabadini and R.F.C. Walters, 
arXiv:0909.4136]. The extra expressiveness of the algebra permits the description of hierarchical systems, and ones with evolving geometry. We make a comparison with the probabilistic automata of Lynch et al. [SIAM J. Comput. 37 (2007) 977-1013].

DOI : https://doi.org/10.1051/ita/2011015
Classification:  18B20,  60J10,  18D10,  05C22
Keywords: categorical algebra, Markov process, weighted automaton, hierarchical, distributed
@article{ITA_2011__45_1_117_0,
     author = {de Francesco Albasini, L. and Sabadini, N. and Walters, R. F. C.},
     title = {The compositional construction of Markov processes II},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {1},
     year = {2011},
     pages = {117-142},
     doi = {10.1051/ita/2011015},
     zbl = {1216.18005},
     mrnumber = {2776857},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2011__45_1_117_0}
}
de Francesco Albasini, L.; Sabadini, N.; Walters, R. F. C. The compositional construction of Markov processes II. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 45 (2011) no. 1, pp. 117-142. doi : 10.1051/ita/2011015. http://www.numdam.org/item/ITA_2011__45_1_117_0/

[1] C. Baier, M. Grösser and F. Ciesinski, Model checking linear-time properties of probabilistic systems. Handbook of Weighted Automata. EATCS Monographs in Theoretical Computer Science (2009), 519-596. | MR 2777739

[2] A. Blass, Seven trees in one. J. Pure Appl. Algebra 103 (1991) 1-21. | MR 1354064 | Zbl 0846.18002

[3] S.L. Bloom and Z. Ésik, Iteration Theories. EATCS Monographs on Theoretical Computer Science (1993). | MR 1295433 | Zbl 0773.03033

[4] R. Blute, A. Edalat and P. Panangaden, Bisimulation for Labelled Markov Processes, Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science (1997), 95-106. | Zbl 1096.68103

[5] A. Carboni and R.F.C. Walters, Cartesian bicategories I. J. Pure Appl. Algebra 49 (1987) 11-32. | MR 920513 | Zbl 0637.18003

[6] B. Coecke and D. Pavlovic, Quantum measurements without sums, in Mathematics of Quantum Computing and Technology. G. Chen, L. Kauffman and S. Lamonaco, Eds. Chapman & Hall (2007), 567-604. | MR 2422232 | Zbl 1139.81307

[7] B. Coecke and S. Perdrix, Environment and classical channels in categorical quantum mechanics. arXiv:1004.1598 (2010). | MR 2755305 | Zbl 1287.81038

[8] L. De Francesco Albasini, N. Sabadini and R.F.C. Walters, The parallel composition of processes, ART 2008. Analysing Reduction systems using Transition systems, Forum, Udine (2008), 111-121 (also arXiv:0904.3961).

[9] L. De Francesco Albasini, N. Sabadini and R.F.C. Walters, The compositional construction of Markov processes. arXiv:0901.2434.

[10] L. De Francesco Albasini, N. Sabadini and R.F.C. Walters, Cospans and spans of graphs: a categorical algebra for the sequential and parallel composition of discrete systems. arXiv:0909.4136.

[11] M. Droste, W. Kuich and H. Vogler, Eds., Handbook of Weighted Automata. EATCS Monographs in Theoretical Computer Science (2009). | MR 2777706 | Zbl 1200.68001

[12] S. Eilenberg, Automata, Languages, and Machines A. Academic Press, New York (1974). | MR 530382 | Zbl 0359.94067

[13] D. Harel, Statecharts: a visual formalism for complex systems. Sci. Comput. Program. 8 (1987) 231-274. | MR 896004 | Zbl 0637.68010

[14] M. Hasegawa, On traced monoidal closed categories. Math. Struct. Comput. Sci. 19 (2009) 217-244. | MR 2496357 | Zbl 1165.18007

[15] J. Hillston, A Compositional Approach to Performance Modelling. Cambridge University Press (1996). | MR 1427945 | Zbl 1080.68003

[16] C.A.R. Hoare, Communicating Sequential Processes. Prentice Hall (1985). | MR 805324 | Zbl 0841.68042

[17] A. Joyal, R. Street and D. Verity, Traced monoidal categories. Math. Proc. Cambridge Philos. Soc. 119 (1996) 447-468. | MR 1357057 | Zbl 0845.18005

[18] P. Katis, N. Sabadini and R.F.C. Walters, Span (Graph): A categorical algebra of transition systems, Proc. AMAST '97, SLNCS, Vol. 1349. Springer Verlag (1997), 307-321. | Zbl 0885.18004

[19] P. Katis, N. Sabadini and R.F.C. Walters, A formalisation of the IWIM Model. A. Porto and G.-C. Roman, Eds., in Proc. Coordination 2000. Lecture Notes in Computer Science 1906 (2000) 267-283.

[20] J. Kock, Frobenius algebras and 2D topological Quantum Field Theories. Cambridge University Press (2004). | MR 2037238 | Zbl 1046.57001

[21] F.W. Lawvere, Some remarks on the future of category theory, Proceedings Category Theory 1990. Lecture Notes in Mathematics 1488 (1991) 1-13. | MR 1173000 | Zbl 0779.18001

[22] N.A. Lynch, R. Segala and F.W. Vaandrager, Observing branching structure through probabilistic contexts. SIAM J. Comput. 37 (2007) 977-1013. | MR 2366211 | Zbl 1156.68020

[23] R. Milner, A Calculus of Communicating Systems. Springer Verlag (1980). | MR 590046 | Zbl 0452.68027

[24] A. Pnueli and L. Zuck, Probabilistic verification by tableaux, in Proceedings LICS'86. IEEE Computer Society Press (1986), 322-331. | Zbl 0797.68112

[25] M.O. Rabin, Probabilistic Automata. Inform. Control 6 (1963) 230-245. | Zbl 0182.33602

[26] R. Rosebrugh, N. Sabadini and R.F.C. Walters, Generic commutative separable algebras and cospans of graphs. Theory and Applications of Categories 15 (2005) 264-177. | MR 2210579 | Zbl 1087.18003

[27] R. Segala, Modeling and Verification of Randomized Distributed Real-Time Systems, Ph.D. thesis, MIT Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA (1995). Also, Technical Report MIT/LCS/TR-676.

[28] P. Sobociński, A non-interleaving process calculus for multi-party synchronisation, Procedings ICE '09 (2009).

[29] A. Sokolova and E.P. De Vink, Probabilistic automata: system types, parallel composition and comparison. Lecture Notes in Computer Science 2925 (2004) 1-43. | Zbl 1203.68089

[30] Gh. Stefanescu, Network Algebra. Springer Verlag (2000). | MR 1753209 | Zbl 0956.68002

[31] R.J. Van Glabbeek, S.A. Smolka and B. Steffen, Reactive, generative and stratified models of probabilistic processes. Inform. Comput. (1995). | MR 1347332 | Zbl 0832.68042

[32] M. Vardi, Automatic verification of probabilistic concurrent finite-state programs, in Proceedings FOCS'85. IEEE Computer Society Press (1985), 327-338.