{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:29:02Z","timestamp":1761611342500,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>Normally, one thinks of probabilistic transition systems as taking an initial probability distribution over the state space into a new probability distribution representing the system after a transition. We, however, take a dual view of Markov processes as transformers of bounded measurable functions. This is very much in the same spirit as a \u201cpredicate-transformer\u201d view, which is dual to the state-transformer view of transition systems. We redevelop the theory of labelled Markov processes from this viewpoint; in particular, we explore approximation theory. We obtain three main results.<\/jats:p>\n          <jats:p>(i) It is possible to define bisimulation on general measure spaces and show that it is an equivalence relation. The logical characterization of bisimulation can be done straightforwardly and generally.<\/jats:p>\n          <jats:p>(ii) A new and flexible approach to approximation based on averaging can be given. This vastly generalizes and streamlines the idea of using conditional expectations to compute approximations.<\/jats:p>\n          <jats:p>(iii) We show that there is a minimal process bisimulation-equivalent to a given process, and this minimal process is obtained as the limit of the finite approximants.<\/jats:p>","DOI":"10.1145\/2537948","type":"journal-article","created":{"date-parts":[[2014,2,4]],"date-time":"2014-02-04T14:16:21Z","timestamp":1391523381000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Approximating Markov Processes by Averaging"],"prefix":"10.1145","volume":"61","author":[{"given":"Philippe","family":"Chaput","sequence":"first","affiliation":[{"name":"McGill University"}]},{"given":"Vincent","family":"Danos","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}]},{"given":"Prakash","family":"Panangaden","sequence":"additional","affiliation":[{"name":"McGill University"}]},{"given":"Gordon","family":"Plotkin","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}]}],"member":"320","published-online":{"date-parts":[[2014,1]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","unstructured":"Arendt W. Grabosch A. Greiner G. Groh U. Lotz H. Moustakas U. Nagel R. Neubrander F. and Schlotterbeck U. 1986. One-Parameter Semigroups of Positive Operators. Springer-Verlag.","DOI":"10.5555\/21743"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1373322"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.019"},{"volume-title":"Probability and Measure","author":"Billingsley P.","key":"e_1_2_2_4_1","unstructured":"Billingsley, P. 1995. Probability and Measure. Wiley-Interscience."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/788019.788852"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/QEST.2005.4"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31982-5_8"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-8.3.321"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/788023.789070"},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Danos V. Desharnais J. and Panangaden P. 2003. Conditional expectation and the approximation of labelled Markov processes. In Proceedings of CONCUR\u201903 - Concurrency Theory. R. Amadio and D. Lugiez Eds. Lecture Notes in Computer Science vol. 2761 Springer-Verlag 477--491.","DOI":"10.1007\/978-3-540-45187-7_31"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.02.004"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/646251.685689"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00035-3"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/788020.788888"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/788022.789028"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.2962"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00051-8"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.09.013"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1759210.1759307"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1212357"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1721918"},{"key":"e_1_2_2_22_1","unstructured":"Dudley R. M. 1989. Real Analysis and Probability. Wadsworth and Brookes\/Cole."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129599002819"},{"volume-title":"Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence. 201--208","author":"Ferns N.","key":"e_1_2_2_24_1","unstructured":"Ferns, N., Panangaden, P., and Precup, D. 2005. Metrics for Markov decision processes with infinite state spaces. In Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence. 201--208."},{"volume-title":"Selected Topics in the Study of Markov Operators. Carolina Lecture Series, 9","author":"Foguel S. R.","key":"e_1_2_2_25_1","unstructured":"Foguel, S. R. 1980. Selected Topics in the Study of Markov Operators. Carolina Lecture Series, 9. University of North Carolina, Chapel Hill, NC."},{"volume-title":"Categorical Aspects of Topology and Analysis","author":"Giry M.","key":"e_1_2_2_26_1","unstructured":"Giry, M. 1981. A categorical approach to probability theory. In Categorical Aspects of Topology and Analysis, B. B. Ski Ed., Lecture Notes in Mathematics, vol. 915, Springer-Verlag, 68--85."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394539.2394629"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2392389.2392440"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.34"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792803.1792826"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792803.1792808"},{"key":"e_1_2_2_32_1","volume-title":"Measure Theory. Number 18 in Graduate Texts in Mathematics","author":"Halmos P.","year":"1950","unstructured":"Halmos, P. 1974. Measure Theory. Number 18 in Graduate Texts in Mathematics, Springer-Verlag. (Originally published in 1950.)"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.2460"},{"key":"e_1_2_2_35_1","first-page":"13","article-title":"The general temporally discrete Markoff process","volume":"3","author":"Hopf E.","year":"1954","unstructured":"Hopf, E. 1954. The general temporally discrete Markoff process. J. Ration. Math. Mech. Anal. 3, 13--45.","journal-title":"J. Ration. Math. Mech. Anal."},{"volume-title":"Proceedings of 8th Annual IEEE Symposium on Logic in Computer Science. 418--427","author":"Joyal A.","key":"e_1_2_2_36_1","unstructured":"Joyal, A., Nielsen, M., and Winskel, G. 1993. Bisimulation and open maps. In Proceedings of 8th Annual IEEE Symposium on Logic in Computer Science. 418--427."},{"key":"e_1_2_2_37_1","first-page":"207","article-title":"Approximation theorems for Markov operators","volume":"21","author":"Kim C.-W.","year":"1972","unstructured":"Kim, C.-W. 1972. Approximation theorems for Markov operators. Prob. Theory Relat. Fields 21, 3, 207--214.","journal-title":"Prob. Theory Relat. Fields"},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Kingman J. F. C. and Taylor S. J. 1966. Introduction to Measure and Probability. Cambridge University Press.","DOI":"10.1017\/CBO9780511897214"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90012-1"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90030-6"},{"key":"e_1_2_2_41_1","doi-asserted-by":"crossref","unstructured":"Mislove M. Ouaknine J. Pavlovic D. and Worrell J. 2004. Duality for labelled Markov processes. In Foundations of Software Science and Computation Structures (FOSSACS). I. Walukiewicz Ed. Lecture Notes in Computer Science vol. 2987 393--407.","DOI":"10.1007\/978-3-540-24727-2_28"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1717290"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/11784180_24"},{"volume-title":"Real and Complex Analysis","author":"Rudin W.","key":"e_1_2_2_44_1","unstructured":"Rudin, W. 1966. Real and Complex Analysis. McGraw-Hill."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/646251.685689"},{"volume-title":"Banach Lattices and Positive Operators","author":"Schaefer H. H.","key":"e_1_2_2_46_1","unstructured":"Schaefer, H. H. 1974. Banach Lattices and Positive Operators. Springer-Verlag."},{"key":"e_1_2_2_47_1","volume-title":"Proceedings of the 2nd International Workshop on Quantum Programming Languages. 127--143","author":"Selinger P.","year":"2004","unstructured":"Selinger, P. 2004. Towards a semantics for higher-order quantum computation. In Proceedings of the 2nd International Workshop on Quantum Programming Languages. 127--143. www.mathstat.dal.ca\/~selinger\/papers.htm."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","unstructured":"van Breugel F. and Worrell J. 2001a. An algorithm for quantitative verification of probabilistic systems. In Proceedings of the 12th International Conference on Concurrency Theory (CONCUR\u201901). K. G. Larsen and M. Nielsen Eds. Lecture Notes in Computer Science vol. 2154 Springer-Verlag 336--350.","DOI":"10.5555\/646736.701784"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/646254.684243"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/1754809.1754824"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.12"},{"volume-title":"Probability with Martingales","author":"Williams D.","key":"e_1_2_2_53_1","unstructured":"Williams, D. 1991. Probability with Martingales. CUP, Cambridge."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.2307\/1968993"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2537948","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2537948","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:14Z","timestamp":1750234694000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2537948"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2537948"],"URL":"https:\/\/doi.org\/10.1145\/2537948","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2010-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}