The Measurable Space of Stochastic Processes

• Autorzy: Cardelli L. , Mardare R.

Identyfikatory

DOI

10.3233/FI-2014-1019

• Języki publikacji: EN

Abstrakty

EN

We introduce a stochastic extension of CCS endowed with structural operational semantics expressed in terms of measure theory. The set of processes is organised as a measurable space by the sigma-algebra generated by structural congruence. The structural operational semantics associates to each process a set of measures over the space of processes. The measures encode the rates of the transitions from a process (state of a system) to a measurable set of processes. We prove that the stochastic bisimilarity is a congruence, which extends the structural congruence. In addition to an elegant operational semantics, our calculus provides a canonic way to define metrics on processes that measure how similar two processes are in terms of behaviour.

Słowa kluczowe

EN

Markov processes; stochastic process algebras; structural operational semantics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 131, nr 3-4
• Strony: 351--371
• Opis fizyczny: Bibliogr. 44 poz.

Twórcy

autor

Cardelli L.

• Microsoft Research Cambridge, UK

autor

Mardare R.

• Dept. of Computer Science, Aalborg University, Denmark

Bibliografia

• [1] G. Bacci, G. Bacci, K.G. Larsen, R. Mardare. Computing Behavioral Distances, Compositionally, In Proc. MFCS2013:74-85, 2013.
• [2] G. Bacci, G. Bacci, K.G. Larsen, R. Mardare. The BisimDist Library: Efficient Computation of Bisimilarity Distances for Markovian Models, In Proc. QEST2013:278-281, 2013.
• [3] G. Bacci, G. Bacci, K.G. Larsen, R. Mardare. On-the-Fly Exact Computation of Bisimilarity Distances, In Proc. TACAS2013:1-15, 2013.
• [4] G. Bacci, M. Miculan. Measurable stochastics for Brane Calculus. TCS.431: 117-136, 2012.
• [5] G. Bacci, M. Miculan. Structural Operational Semantics for Continuous State Probabilistic Processes. In Proc. CMCS2012: 71-89, 2012.
• [6] G. Berry, G. Boudol. The Chemical Abstract Machine, In Proc. POPL 1990:81-94.
• [7] J.A. Bergstra et al (Eds.) Handbook of Process Algebra. Elsevier, 2001.
• [8] M. Bernardo, R. Gorrieri. A tutorial on EMPA: A theory of concurrent processes with nondeterminism, priorities, probabilities and time. TCS 202(1-2):1-54, 1998.
• [9] R. Blute et al. Bisimulation for labeled Markov processes. In Proc. LICS’97, IEEE Press, 1997.
• [10] M. Calder et al. Automatically deriving ODEs from process algebra models of signaling pathways. In Proc. CMSB’05, 2005.
• [11] C. Calude, S. Marcus, G. Paun, The universal grammar as a hypothetical brain, Revue Roumaine de Linguistique 24 (5), 479-489, 1979
• [12] L. Cardelli, R. Mardare. The Measurable Space of Stochastic Processes. In Proc. QEST’10 2010:171-180, IEEE Press.
• [13] M. Bravetti et al. YMCA: Why Markov Chain Algebra?, ENTCS 162:107-112, 2006.
• [14] V. Danos et al. Bisimulation and Coconguence for Probabilistic Systems, Inf. and Comp. 204(4):503-523, 2006.
• [15] L. de Alfaro et al. Discounting the future in systems theory. LNCS 2719:1022-1037, 2003.
• [16] R. De Nicola et al. Rate-Based Transition Systems for Stochastic Process Calculi. LNCS 5556:435-446, 2009
• [17] E.P. de Vink, J. Rutten, Bisimulation for probabilistic transition systems: A coalgebaic approach. TCS 221(1-2):271-293, 1999.
• [18] J. Desharnais, Labelled Markov Processes. PhD thesis, McGill University, 1999.
• [19] J. Desharnais et al. A logical characterization of bisimulation for labeledMarkov processes. In Proc LICS’98, IEEE Press, 1998.
• [20] J. Desharnais et al. Bisimulation for labeled Markov Processes. Inf. and Comp., 179(2):163-193, 2002.
• [21] J. Desharnais, P. Panangaden. Continous Stochastic Logic Characterizes Bisimulation of Continuous-time Markov Processes. JLAP. 56:99-115, 2003.
• [22] E. Doberkat. Stochastic Relations. Foundations for Markov Transition Systems. Chapman and Hall/CRC, 2007.
• [23] N. Gotz et al. TIPP - A language for timed processes and performance evaluation. Tech.Rep. 4/92 IMMD VII, University of Erlangen-Nurnberg.
• [24] V. Gupta et al. Approximate reasoning for real-time probabilistic processes. LMCS 2(1:4) 2006.
• [25] J. Harsanyi. Games with incomplete information played by bayesian players, part one. Management Sci., 14:159-182, 1967.
• [26] J. Hillston. A compositional approach to performance modelling. Cambridge University Press, 1996.
• [27] J. Hillston. Process algebras for quantitative analysis. In Proc. LICS’05, IEEE Press, 2005.
• [28] H. Hermanns. Interactive Markov Chains. LNCS 2428, 2008.
• [29] B. Klin, V. Sassone. Structural Operational Semantics for Stochastic Process Calculi. LNCS 4968:428-442, 2008.
• [30] M. Kwiatkowska et al. Automatic Verification of Real-Time Systems With Discrete Probability Distributions. LNCS 1601:79-95, 1999.
• [31] K. G. Larsen and A. Skou. Bisimulation through probabilistic testing. Inf. and Comp., 94:1-28, 1991.
• [32] P. D. Lincoln et al. A probabilistic poly-time framework for protocol analysis. ACM(CCS-5), 1998.
• [33] S. Marcus, Membranes Versus DNA, Fundam. Inform., 49(1-3), pp 223-227, 2002
• [34] R. Milner. A calculus of communicating systems. J. of ACM, 1980.
• [35] L.S. Moss, I.D. Viglizzo. Harsanyi type spaces and final coalgebras constructed from satisfied theories. ENTCS 106:279-295, 2004.
• [36] P. Panangaden. Labelled Markov Processes. Imperial College Press, 2009.
• [37] C. Priami. Stochastic π-Calculus. Computer Journal, 38(7):578-589, 1995.
• [38] J. Rutten. Universal coalgebra: a theory of systems, TCS, 249:3-80, 2000.
• [39] R. Segala, N. Lynch. Probabilistic Simulations for Probabilistic Processes, Nordic J. of Comp., 2(2):250-273, 1995.
• [40] D. Turi, G.D. Plotkin. Towards a mathematical operational semantics, In Proc. Lics’97, IEEE Press, 1997.
• [41] A.M. Turing. Computing Machinery and Intelligence, Mind 59, pp 433-460, 1950
• [42] A.M. Turing. The Chemical Basis of Morphogenesis, Phil. Trans. R. Soc. London B 237 pp 37-72, 1952
• [43] F. van Breugel, J. Worrell. An algorithm for quantitative verification of probabilistic systems. LNCS 2154:336-350, 2001.
• [44] R. J. van Glabbeek et al. Reactive, Generative and Stratified Models of Probabilistic Processes. Inf. And Comp. 121(1):59-80, 1995.