The compositional construction of Markov processes II

L. de Francesco Albasini; N. Sabadini; R. F.C. Walters

RAIRO - Theoretical Informatics and Applications (2011)

  • Volume: 45, Issue: 1, page 117-142
  • ISSN: 0988-3754

Abstract

top
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].

How to cite

top

de Francesco Albasini, L., Sabadini, N., and Walters, R. F.C.. "The compositional construction of Markov processes II." RAIRO - Theoretical Informatics and Applications 45.1 (2011): 117-142. <http://eudml.org/doc/221943>.

@article{deFrancescoAlbasini2011,
abstract = { 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]. },
author = {de Francesco Albasini, L., Sabadini, N., Walters, R. F.C.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Categorical algebra; Markov process; weighted automaton; hierarchical; distributed; categorical algebra; probabilistic automata},
language = {eng},
month = {3},
number = {1},
pages = {117-142},
publisher = {EDP Sciences},
title = {The compositional construction of Markov processes II},
url = {http://eudml.org/doc/221943},
volume = {45},
year = {2011},
}

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
DA - 2011/3//
PB - EDP Sciences
VL - 45
IS - 1
SP - 117
EP - 142
AB - 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].
LA - eng
KW - Categorical algebra; Markov process; weighted automaton; hierarchical; distributed; categorical algebra; probabilistic automata
UR - http://eudml.org/doc/221943
ER -

References

top
  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.  
  2. A. Blass, Seven trees in one. J. Pure Appl. Algebra103 (1991) 1–21.  
  3. S.L. Bloom and Z. Ésik, Iteration Theories. EATCS Monographs on Theoretical Computer Science (1993).  
  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.  
  5. A. Carboni and R.F.C. Walters, Cartesian bicategories I. J. Pure Appl. Algebra49 (1987) 11–32.  
  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.  
  7. B. Coecke and S. Perdrix, Environment and classical channels in categorical quantum mechanics. arXiv:1004.1598 (2010).  
  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).  
  12. S. Eilenberg, Automata, Languages, and Machines A. Academic Press, New York (1974).  
  13. D. Harel, Statecharts: a visual formalism for complex systems. Sci. Comput. Program.8 (1987) 231–274.  
  14. M. Hasegawa, On traced monoidal closed categories. Math. Struct. Comput. Sci.19 (2009) 217–244.  
  15. J. Hillston, A Compositional Approach to Performance Modelling. Cambridge University Press (1996).  
  16. C.A.R. Hoare, Communicating Sequential Processes. Prentice Hall (1985).  
  17. A. Joyal, R. Street and D. Verity, Traced monoidal categories. Math. Proc. Cambridge Philos. Soc.119 (1996) 447–468.  
  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.  
  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 Science1906 (2000) 267–283.  
  20. J. Kock, Frobenius algebras and 2D topological Quantum Field Theories. Cambridge University Press (2004).  
  21. F.W. Lawvere, Some remarks on the future of category theory, Proceedings Category Theory 1990. Lecture Notes in Mathematics1488 (1991) 1–13.  
  22. N.A. Lynch, R. Segala and F.W. Vaandrager, Observing branching structure through probabilistic contexts. SIAM J. Comput.37 (2007) 977–1013.  
  23. R. Milner, A Calculus of Communicating Systems. Springer Verlag (1980).  
  24. A. Pnueli and L. Zuck, Probabilistic verification by tableaux, in Proceedings LICS'86. IEEE Computer Society Press (1986), 322–331.  
  25. M.O. Rabin, Probabilistic Automata. Inform. Control6 (1963) 230–245.  
  26. R. Rosebrugh, N. Sabadini and R.F.C. Walters, Generic commutative separable algebras and cospans of graphs. Theory and Applications of Categories15 (2005) 264–177.  
  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 Science2925 (2004) 1–43.  
  30. Gh. Stefanescu, Network Algebra. Springer Verlag (2000).  
  31. R.J. van Glabbeek, S.A. Smolka and B. Steffen, Reactive, generative and stratified models of probabilistic processes. Inform. Comput. (1995).  
  32. M. Vardi, Automatic verification of probabilistic concurrent finite-state programs, in Proceedings FOCS'85. IEEE Computer Society Press (1985), 327–338.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.