Abstract
We consider the problem of modeling syntax and semantics of probabilistic processes with continuous states (e.g. with continuous data). Syntax and semantics of these systems can be defined as algebras and coalgebras of suitable endofunctors over Meas, the category of measurable spaces. In order to give a more concrete representation for these coalgebras, we present an SOS-like rule format which induces an abstract GSOS over Meas; this format is proved to yield a fully abstract universal semantics, for which behavioural equivalence is a congruence.
To this end, we solve several problems. In particular, the format has to specify how to compose the semantics of processes (which basically are continuous state Markov processes). This is achieved by defining a language of measure terms, i.e., expressions specifically designed for describing probabilistic measures. Thus, the transition relation associates processes with measure terms.
As an example application, we model a CCS-like calculus of processes placed in an Euclidean space. The approach we follow in this case can be readily adapted to other quantitative aspects, e.g. Quality of Service, physical and chemical parameters in biological systems, etc.
Work supported by MIUR PRIN project 20088HXMYN, “SisteR”.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abbott, E.A.: Flatland: A Romance of Many Dimensions. Blackwell (1884)
Adámek, J., Trnková, V.: Automata and Algebras in Categories, 1st edn. Kluwer Academic Publishers, Norwell (1990)
Bacci, G., Miculan, M.: Measurable stochastics for Brane Calculus. Theoretical Comput. Sci. 431, 117–136 (2012), doi:10.1016/j.tcs.2011.12.055
Barbuti, R., Maggiolo-Schettini, A., Milazzo, P., Pardini, G.: Spatial calculus of looping sequences. Electr. Notes Theor. Comput. Sci. 229(1), 21–39 (2009)
Barr, M.: Algebraically compact functors. Journal of Pure and Applied Algebra 82(3), 211–231 (1992)
Bartels, F.: On Generalised Coinduction and Probabilistic Specification Formats: Distributive Laws in Coalgebraic Modelling. PhD thesis, CWI, Amsterdam (2004)
Bartels, F., Sokolova, A., de Vink, E.P.: A hierarchy of probabilistic system types. Electr. Notes Theor. Comput. Sci. 82(1) (2003)
Bloom, B., Istrail, S., Meyer, A.R.: Bisimulation can’t be traced. J. ACM 42(1), 232–268 (1995)
Brodo, L., Degano, P., Gilmore, S., Hillston, J., Priami, C.: Performance Evaluation for Global Computation. In: Priami, C. (ed.) GC 2003. LNCS, vol. 2874, pp. 229–253. Springer, Heidelberg (2003)
Cardelli, L., Gardner, P.: Processes in Space. In: Ferreira, F., Löwe, B., Mayordomo, E., Mendes Gomes, L. (eds.) CiE 2010. LNCS, vol. 6158, pp. 78–87. Springer, Heidelberg (2010)
Cardelli, L., Mardare, R.: The measurable space of stochastic processes. In: Proc. QEST, pp. 171–180. IEEE Computer Society (2010)
Danos, V., Desharnais, J., Laviolette, F., Panangaden, P.: Bisimulation and cocongruence for probabilistic systems. Inf. Comput. 204(4), 503–523 (2006)
de Vink, E.P., Rutten, J.: Bisimulation for Probabilistic Transition Systems: A Coalgebraic Approach. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol. 1256, pp. 460–470. Springer, Heidelberg (1997)
Desharnais, J., Edalat, A., Panangaden, P.: Bisimulation for labelled Markov processes. Inf. Comput. 179(2), 163–193 (2002)
Ding, J., Hillston, J.: Structural Analysis for Stochastic Process Algebra Models. In: Johnson, M., Pavlovic, D. (eds.) AMAST 2010. LNCS, vol. 6486, pp. 1–27. Springer, Heidelberg (2011)
Doberkat, E.-E.: Stochastic relations: foundations for Markov transition systems. Chapman & Hall/CRC Studies in Informatics Series. Chapman & Hall/CRC (2007)
Giry, M.: A categorical approach to probability theory. In: Banaschewski (ed.) Categorical Aspects of Topology and Analysis. Lecture Notes in Mathematics, vol. 915, pp. 68–85. Springer, Heidelberg (1982)
Hermanns, H., Herzog, U., Katoen, J.-P.: Process algebra for performance evaluation. Theor. Comput. Sci. 274(1-2), 43–87 (2002)
Hillston, J.: Process algebras for quantitative analysis. In: Proc. LICS, pp. 239–248. IEEE Computer Society (2005)
Klin, B., Sassone, V.: Structural Operational Semantics for Stochastic Process Calculi. In: Amadio, R.M. (ed.) FOSSACS 2008. LNCS, vol. 4962, pp. 428–442. Springer, Heidelberg (2008)
Kurz, A.: Logics for Coalgebras and Applications to Computer Science. PhD thesis, Ludwig-Maximilians-Universität München (2000)
Larsen, K.G., Skou, A.: Bisimulation through probabilistic testing. Information and Computation 94(1), 1–28 (1991)
Moss, L.S., Viglizzo, I.D.: Final coalgebras for functors on measurable spaces. Inf. Comput. 204(4), 610–636 (2006)
Panangaden, P.: Labelled Markov Processes. Imperial College Press (2009)
Plotkin, G.D.: A structural approach to operational semantics. DAIMI FN-19, Computer Science Department, Århus University, Århus (1981)
Smyth, M.B., Plotkin, G.D.: The category-theoretic solution of recursive domain equations. SIAM J. Comput. 11(4), 761–783 (1982)
Sokolova, A.: Probabilistic systems coalgebraically: A survey. Theoretical Comput. Sci. 412(38), 5095–5110 (2011)
Staton, S.: Relating coalgebraic notions of bisimulation. Logical Methods in Computer Science 7(1) (2011)
Turi, D., Plotkin, G.: Towards a mathematical operational semantics. In: Proc. 12th LICS Conf., pp. 280–291. IEEE Computer Society Press (1997)
Viglizzo, I.D.: Final Sequences and Final Coalgebras for Measurable Spaces. In: Fiadeiro, J.L., Harman, N.A., Roggenbach, M., Rutten, J. (eds.) CALCO 2005. LNCS, vol. 3629, pp. 395–407. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 IFIP International Federation for Information Processing
About this paper
Cite this paper
Bacci, G., Miculan, M. (2012). Structural Operational Semantics for Continuous State Probabilistic Processes. In: Pattinson, D., Schröder, L. (eds) Coalgebraic Methods in Computer Science. CMCS 2012. Lecture Notes in Computer Science, vol 7399. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32784-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-32784-1_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32783-4
Online ISBN: 978-3-642-32784-1
eBook Packages: Computer ScienceComputer Science (R0)