×

zbMATH — the first resource for mathematics

Categories of timed stochastic relations. (English) Zbl 1337.68195
Abramsky, Samson (ed.) et al., Proceedings of the 25th conference on the mathematical foundations of programming semantics (MFPS 2009), Oxford, UK, April 3–7, 2009. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 249, 193-217 (2009).
Summary: Stochastic behavior – the probabilistic evolution of a system in time – is essential to modeling the complexity of real-world systems. It enables realistic performance modeling, quality-of-service guarantees, and especially simulations for biological systems. Languages like the stochastic pi calculus have emerged as effective tools to describe and reason about systems exhibiting stochastic behavior. These languages essentially denote continuous-time stochastic processes, obtained through an operational semantics in a probabilistic transition system. In this paper we seek a more descriptive foundation for the semantics of stochastic behavior using categories and monads. We model a first-order imperative language with stochastic delay by identifying probabilistic choice and delay as separate effects, modeling each with a monad, and combining the monads to build a model for the stochastic language.
For the entire collection see [Zbl 1281.68012].

MSC:
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
18C15 Monads (= standard construction, triple or triad), algebras for monads, homology and derived functors for monads
18C50 Categorical semantics of formal languages
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Software:
Bio-PEPA; BlenX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abramsky, S., Retracing some paths in process algebra, (), 1-17
[2] Adámek, J.; Herrlich, H.; Strecker, G.E., Abstract and concrete categories: the joy of cats, (1990), John Wiley & Sons · Zbl 0695.18001
[3] Alur, R.; Dill, D.L., A theory of timed automata, Theoretical computer science, 126, 183-235, (1994) · Zbl 0803.68071
[4] Asarin, E.; Caspi, P.; Maler, O., Timed regular expressions, Journal of the ACM, 49, 172-206, (2002) · Zbl 1323.68335
[5] Ash, R.B.; Doléans-Dade, C.A., Probability & measure theory, (1999), Academic Press
[6] Barr, M.; Wells, C., Toposes, triples and theories, Grundlehren der mathematischen wissenschaften, 278, (1985), Springer-Verlag New York · Zbl 0567.18001
[7] Beck, J., Distributive laws, (), 119-140
[8] Bernardo, M.; Gorrieri, R., A tutorial on EMPA: A theory of concurrent processes with nondeterminism, priorities, probabilities and time, Theoretical computer science, 202, 1-54, (1998) · Zbl 0902.68075
[9] Billingsley, P., Probability and measure, (1995), Wiley-Interscience · Zbl 0822.60002
[10] Bortolussi, L.; Policriti, A., Modeling biological systems in stochastic concurrent constraint programming, Constraints, 13, 66-90, (2008) · Zbl 1144.92001
[11] Bowman, H.; Blair, L.; Blair, G.S.; Chetwynd, A., Formal specification of distributed multimedia systems, (1998), University College London Press
[12] Brown, D. and R. Pucella, Categories of timed stochastic relations, Technical Report NU-CCIS-09-02, Northeastern University (2009) · Zbl 1337.68195
[13] Bryans, J.; Bowman, H.; Derrick, J., Model checking stochastic automata, ACM transactions on computational logic, 4, 452-492, (2003) · Zbl 1365.68316
[14] Ciocchetta, F.; Hillston, J., Bio-PEPA: an extension of the process algebra PEPA for biochemical networks, Electronic notes in theoretical computer science, 194, 103-117, (2008) · Zbl 1279.68254
[15] D’Argenio, P., “Algebras and automata for timed and stochastic systems,” Ph.D. thesis, University of Twente, Enschede, The Netherlands (1999)
[16] D’Argenio, P.R.; Katoen, J.-P., A theory of stochastic systems part I: stochastic automata, Information and computation, 203, 1-38, (2005) · Zbl 1105.68061
[17] Dematté, L.; Priami, C.; Romanel, A., Modelling and simulation of biological processes in blenx, SIGMETRICS performance evaluation review, 35, 32-39, (2008) · Zbl 1160.68678
[18] Dobertkat, E.-E., Stochastic relations: foundations for Markov transition systems, (2007), Chapman & Hall/CRC
[19] Folland, G.B., Real analysis: modern techniques and their applications, (1984), Wiley-Interscience · Zbl 0549.28001
[20] Gibbons, J., Conditionals in distributive categories, Technical report, Oxford Brookes University (1997)
[21] Giry, M., A categorical approach to probability theory, (), 68-85
[22] Glynn, P.W., A GSMP formalism for discrete event simulation, Proceedings of the IEEE, 77, 14-23, (1989)
[23] Götz, N., U. Herzog and M. Rettelbach, Multiprocessor and distributed system design: The integration of functional specification and performance analysis using stochastic process algebras, in: Performance/SIGMETRICS Tutorials, 1993, pp. 121-146
[24] Gunter, C.A., Semantics of programming languages: structures and techniques, (1992), MIT Press · Zbl 0823.68059
[25] Haghverdi, E., “A Categorical Approach to Linear Logic, Geometry of Proofs and Full Completeness,” Ph.D. thesis, University of Ottawa (2000) · Zbl 0951.03062
[26] Hillston, J., “A Compositional Approach to Performance Modelling,” Distinguished Dissertations in Computer Science, Cambridge University Press, 1996 · Zbl 1080.68003
[27] Hillston, J., Process algebras for quantitative analysis, in: Proc. 20th Annual IEEE Symposium on Logic in Computer Science (LICS’05) (2005), pp. 239-248
[28] Jones, C. and G.D. Plotkin, A probabilistic powerdomain of evaluations, in: Proc. 4th Annual IEEE Symposium on Logic in Computer Science (LICS’89) (1989), pp. 186-195 · Zbl 0716.06003
[29] Kallenberg, O., Foundations of modern probability, (2002), Springer-Verlag · Zbl 0996.60001
[30] Kleinrock, L., Queueing systems, volume I: theory, (1975), John Wiley & Sons
[31] Klin, B.; Sassone, V., Structural operational semantics for stochastic process calculi, (), 428-442 · Zbl 1138.68468
[32] Kozen, D., Semantics of probabilistic programs, Journal of computer and systems sciences, 22, 328-350, (1981) · Zbl 0476.68019
[33] Kozen, D., A probabilistic PDL, Journal of computer and systems sciences, 30, 162-178, (1985) · Zbl 0575.03013
[34] Lawvere, F.W., The category of probabilistic mappings (1962), unpublished manuscript
[35] Manes, E.; Arbib, M., Algebraic approaches to program semantics, (1986), Springer-Verlag · Zbl 0599.68008
[36] Marsam, M.A.; Conte, G.; Balbo, G., A class of generalised stochastic Petri nets for the performance evaluation of multiprocessor systems, ACM transactions on computer systems, 2, 93-122, (1984)
[37] Moggi, E., Computational lambda-calculus and monads, in: Proc. 4th Annual IEEE Symposium on Logic in Computer Science (LICS’89) (1989), pp. 14-23 · Zbl 0716.03007
[38] Moggi, E., Notions of computation and monads, Information and computation, 93, 55-92, (1991) · Zbl 0723.68073
[39] Mulry, P.S., Lifting theorems for kleisli categories, (), 304-319
[40] Mulry, P.S., Lifting results for categories of algebras, Theoretical computer science, 278, 257-269, (2002) · Zbl 1002.68088
[41] Panangaden, P., The category of Markov kernels, Proc. 1st international workshop on probabilistic methods in verification, (PROBMIV’98), Electronic notes in theoretical computer science, 22, 171-187, (1999)
[42] Pierce, B.C., Types and programming languages, (2002), MIT Press Cambridge, MA, USA
[43] Priami, C., Stochastic pi calculus, The computer journal, 38, 578-589, (1995)
[44] Priami, C., Stochastic pi-calculus with general distributions, in: Proc. 4th Workshop on Process Algebras and Performance Modelling (PAPM ’96), 1996, pp. 41-57
[45] Priami, C.; Quaglia, P., Modeling the dynamics of bio-systems, Briefings in bioinformatics, 5, 259-269, (2004)
[46] Priami, C.; Regev, A.; Shapiro, E.; Silverman, W., Application of a stochastic name-passing calculus to representation and simulation of molecular processes, Information processing letters, 80, 25-31, (2001) · Zbl 0997.92018
[47] Ramsey, N. and A. Pfeffer, Stochastic lambda calculus and monads of probability distributions, in: Proc. 29th Annual ACM Symposium on Principles of Programming Languages (POPL’02) (2002), pp. 154-165 · Zbl 1323.68150
[48] Saheb-Djahromi, N., CPOs of measures for nondeterminism, Theoretical computer science, 12, 19-37, (1980) · Zbl 0433.68017
[49] Szigeti, J., On limits and colimits in the kleisli category, Cahiers de topologie et Géométrie différentielle catégoriques, 24, 381-391, (1983) · Zbl 0533.18006
[50] van Breugel, F., The metric monad for probabilistic nondeterminism (2005), unpublished manuscript, available from http://www.cse.yorku.ca/ franck/research/drafts
[51] Varacca, D.; Winskel, G., Distributing probability over non-determinism, Mathematical structures in computer science, 16, 87-113, (2006) · Zbl 1093.18002
[52] Winskel, G., The formal semantics of programming languages, (1993), MIT Press · Zbl 0919.68082
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.