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].
Mots-clés : 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},
pages = {117--142},
publisher = {EDP-Sciences},
volume = {45},
number = {1},
year = {2011},
doi = {10.1051/ita/2011015},
mrnumber = {2776857},
zbl = {1216.18005},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2011015/}
}
TY - JOUR AU - de Francesco Albasini, L. AU - Sabadini, N. AU - Walters, R. F. C. TI - The compositional construction of Markov processes II JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2011 SP - 117 EP - 142 VL - 45 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2011015/ DO - 10.1051/ita/2011015 LA - en ID - ITA_2011__45_1_117_0 ER -
%0 Journal Article %A de Francesco Albasini, L. %A Sabadini, N. %A Walters, R. F. C. %T The compositional construction of Markov processes II %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2011 %P 117-142 %V 45 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2011015/ %R 10.1051/ita/2011015 %G en %F 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, Tome 45 (2011) no. 1, pp. 117-142. doi : 10.1051/ita/2011015. http://www.numdam.org/articles/10.1051/ita/2011015/
[1] , and , Model checking linear-time properties of probabilistic systems. Handbook of Weighted Automata. EATCS Monographs in Theoretical Computer Science (2009), 519-596. | MR
[2] , Seven trees in one. J. Pure Appl. Algebra 103 (1991) 1-21. | MR | Zbl
[3] and , Iteration Theories. EATCS Monographs on Theoretical Computer Science (1993). | MR | Zbl
[4] , and , Bisimulation for Labelled Markov Processes, Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science (1997), 95-106. | Zbl
[5] and , Cartesian bicategories I. J. Pure Appl. Algebra 49 (1987) 11-32. | MR | Zbl
[6] and , 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 | Zbl
[7] and , Environment and classical channels in categorical quantum mechanics. arXiv:1004.1598 (2010). | MR | Zbl
[8] , and , The parallel composition of processes, ART 2008. Analysing Reduction systems using Transition systems, Forum, Udine (2008), 111-121 (also arXiv:0904.3961).
[9] , and , The compositional construction of Markov processes. arXiv:0901.2434.
[10] , and , Cospans and spans of graphs: a categorical algebra for the sequential and parallel composition of discrete systems. arXiv:0909.4136.
[11] , and , Eds., Handbook of Weighted Automata. EATCS Monographs in Theoretical Computer Science (2009). | MR | Zbl
[12] , Automata, Languages, and Machines A. Academic Press, New York (1974). | MR | Zbl
[13] , Statecharts: a visual formalism for complex systems. Sci. Comput. Program. 8 (1987) 231-274. | MR | Zbl
[14] , On traced monoidal closed categories. Math. Struct. Comput. Sci. 19 (2009) 217-244. | MR | Zbl
[15] , A Compositional Approach to Performance Modelling. Cambridge University Press (1996). | MR | Zbl
[16] , Communicating Sequential Processes. Prentice Hall (1985). | MR | Zbl
[17] , and , Traced monoidal categories. Math. Proc. Cambridge Philos. Soc. 119 (1996) 447-468. | MR | Zbl
[18] , and , Span (Graph): A categorical algebra of transition systems, Proc. AMAST '97, SLNCS, Vol. 1349. Springer Verlag (1997), 307-321. | Zbl
[19] , and , 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] , Frobenius algebras and 2D topological Quantum Field Theories. Cambridge University Press (2004). | MR | Zbl
[21] , Some remarks on the future of category theory, Proceedings Category Theory 1990. Lecture Notes in Mathematics 1488 (1991) 1-13. | MR | Zbl
[22] , and , Observing branching structure through probabilistic contexts. SIAM J. Comput. 37 (2007) 977-1013. | MR | Zbl
[23] , A Calculus of Communicating Systems. Springer Verlag (1980). | MR | Zbl
[24] and , Probabilistic verification by tableaux, in Proceedings LICS'86. IEEE Computer Society Press (1986), 322-331. | Zbl
[25] , Probabilistic Automata. Inform. Control 6 (1963) 230-245. | Zbl
[26] , and , Generic commutative separable algebras and cospans of graphs. Theory and Applications of Categories 15 (2005) 264-177. | MR | Zbl
[27] , 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] , A non-interleaving process calculus for multi-party synchronisation, Procedings ICE '09 (2009).
[29] and , Probabilistic automata: system types, parallel composition and comparison. Lecture Notes in Computer Science 2925 (2004) 1-43. | Zbl
[30] , . Springer Verlag (2000). | MR | Zbl
[31] , and , Reactive, generative and stratified models of probabilistic processes. Inform. Comput. (1995). | MR | Zbl
[32] , Automatic verification of probabilistic concurrent finite-state programs, in Proceedings FOCS'85. IEEE Computer Society Press (1985), 327-338.
Cité par Sources :
