×

Approximating Markov processes by averaging. (English) Zbl 1295.68167


MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
60J35 Transition functions, generators and resolvents
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Software:

QPL
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] 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. · Zbl 0585.47030 · doi:10.1007/BFb0074922
[2] Baier, C. and Katoen, J.-P. 2008.Principles of Model Checking. MIT Press. · Zbl 1179.68076
[3] Bartels, F., Sokolova, A., and de Vink, E. 2004. A hierarchy of probabilistic system types.Theoret. Comput. Sci. 327, 3–22. · Zbl 1071.68071 · doi:10.1016/j.tcs.2004.07.019
[4] Billingsley, P. 1995.Probability and Measure. Wiley-Interscience. · Zbl 0822.60002
[5] Blute, R., Desharnais, J., Edalat, A., and Panangaden, P. 1997. Bisimulation for labelled Markov processes. InProceedings of the 12th IEEE Symposium on Logic in Computer Science. · Zbl 1096.68103 · doi:10.1109/LICS.1997.614943
[6] Bouchard-Côté, A., Ferns, N., Panangaden, P., and Precup, D. 2005. An approximation algorithm for labelled Markov processes: Towards realistic approximation. InProceedings of the 2nd International Conference on the Quantitative Evaluation of Systems (QEST). 54–61.
[7] Cattani, S., Segala, R., Kwiatkowska, M., and Norman, G. 2005. Stochastic transition systems for continuous state spaces and non-determinism. InProceedings of the 8th International Conference on Foundations of Software Science and Computational Structures (FOSSACS). Lecture Notes in Computer Science, vol. 3441, 125–139. · Zbl 1118.68568
[8] Choksi, J. 1958. Inverse limits on measure spaces.Proc. London Math. Soc. 8, 3, 321–342. · Zbl 0085.04003 · doi:10.1112/plms/s3-8.3.321
[9] Danos, V. and Desharnais, J. 2003. Labeled Markov Processes: Stronger and faster approximations. InProceedings of the 18th Symposium on Logic in Computer Science. IEEE.
[10] Danos, V., Desharnais, J., and Panangaden, P. 2003. Conditional expectation and the approximation of labelled Markov processes. InProceedings of CONCUR’03 - Concurrency Theory. R. Amadio and D. Lugiez Eds., Lecture Notes in Computer Science, vol. 2761, Springer-Verlag, 477–491. · Zbl 1274.68265
[11] Danos, V., Desharnais, J., Laviolette, F., and Panangaden, P. 2006. Bisimulation and cocongruence for probabilistic systems.Inf. Computat. 204, 4, 503–523. · Zbl 1110.68083 · doi:10.1016/j.ic.2005.02.004
[12] de Vink, E. and Rutten, J. J. M. M. 1997. Bisimulation for probabilistic transition systems: A coalgebraic approach. InProceedings of the 24th International Colloquium on Automata Languages and Programming. · Zbl 0930.68092 · doi:10.1007/3-540-63165-8_202
[13] de Vink, E. and Rutten, J. J. M. M. 1999. Bisimulation for probabilistic transition systems: A coalgebraic approach.Theoret. Comput. Sci. 221, 1/2, 271–293. · Zbl 0930.68092 · doi:10.1016/S0304-3975(99)00035-3
[14] Desharnais, J., Edalat, A., and Panangaden, P. 1998. A logical characterization of bisimulation for labelled Markov processes. InProceedings of the 13th IEEE Symposium on Logic in Computer Science. IEEE, 478–489.
[15] Desharnais, J., Gupta, V., Jagadeesan, R., and Panangaden, P. 2000. Approximation of labeled Markov processes. InProceedings of the 15th Annual IEEE Symposium on Logic in Computer Science. IEEE, 95–106.
[16] Desharnais, J., Edalat, A., and Panangaden, P. 2002. Bisimulation for labeled Markov processes.Inf. Computat. 179, 2, 163–193. · Zbl 1096.68103 · doi:10.1006/inco.2001.2962
[17] Desharnais, J., Gupta, V., Jagadeesan, R., and Panangaden, P. 2003. Approximating labeled Markov processes.Inf. Computat. 184, 1, 160–200. · Zbl 1028.68091 · doi:10.1016/S0890-5401(03)00051-8
[18] Desharnais, J., Gupta, V., Jagadeesan, R., and Panangaden, P. 2004. A metric for labelled Markov processes.Theoret. Comput. Sci. 318, 3, 323–354. · Zbl 1068.68093 · doi:10.1016/j.tcs.2003.09.013
[19] Doberkat, E.-E. 2003. Semi-pullbacks and bisimulations in categories of stochastic relations. InProceedings of the 27th International Colloquium on Automata Languages and Programming (ICALP’03). J. C. M. Baeten, J. K. Lenstra, J. Parrow, and G. J. Woeinger Eds., Lecture Notes in Computer Science, vol. 2719, Springer-Verlag, 996–1007. · Zbl 1041.18006
[20] Doberkat, E.-E. 2007.Stochastic Relations. Foundations for Markov Transition Systems. Chapman and Hall, New York. · Zbl 1137.60002 · doi:10.1201/9781584889427
[21] Doberkat, E.-E. 2010.Stochastic Coalgebraic Logic. Springer-Verlag. · Zbl 1207.03039
[22] Dudley, R. M. 1989.Real Analysis and Probability. Wadsworth and Brookes/Cole. · Zbl 0686.60001
[23] Edalat, A. 1999. Semi-pullbacks and bisimulation in categories of Markov processes.Math. Struct. Comput. Sci. 9, 5, 523–543. · Zbl 0937.18005 · doi:10.1017/S0960129599002819
[24] Ferns, N., Panangaden, P., and Precup, D. 2005. Metrics for Markov decision processes with infinite state spaces. InProceedings of the 21st Conference on Uncertainty in Artificial Intelligence. 201–208.
[25] Foguel, S. R. 1980.Selected Topics in the Study of Markov Operators. Carolina Lecture Series, 9. University of North Carolina, Chapel Hill, NC.
[26] Giry, M. 1981. A categorical approach to probability theory. InCategorical Aspects of Topology and Analysis, B. B. Ski Ed., Lecture Notes in Mathematics, vol. 915, Springer-Verlag, 68–85.
[27] Goubault-Larrecq, J. 2007a. Continuous capacities on continuous state spaces. InProceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP’07). Lecture Notes in Computer Science, vol. 4596, Springer-Verlag, 764–776. · Zbl 1171.91316
[28] Goubault-Larrecq, J. 2007b. Continuous previsions. InProceedings of the 16th Annual EACSL Conference on Computer Science Logic (CSL’07). Lecture Notes in Computer Science, vol. 4646, Springer-Verlag, 542–557. · Zbl 1179.68074
[29] Goubault-Larrecq, J. 2007c. On Noetherian spaces. InProceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science (LICS’07). IEEE, 453–462.
[30] Goubault-Larrecq, J. 2008a. Prevision domains and convex powercones. InProceedings of the 11th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS’08). Lecture Notes in Computer Science, vol. 4962, Springer-Verlag, 318–333. · Zbl 1139.68034
[31] Goubault-Larrecq, J. 2008b. Simulation hemi-metrics between infinite-state stochastic games. InProceedings of the 11th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS’08). Lecture Notes in Computer Science, vol. 4962, Springer-Verlag, 50–65. · Zbl 1139.68041
[32] Halmos, P. 1974.Measure Theory. Number 18 in Graduate Texts in Mathematics, Springer-Verlag. (Originally published in 1950.)
[33] Hawke, P. 2006. Markov operators on Banach lattices. M.S. thesis, University of the Witwatersrand, Johannesburg.
[34] Hennessy, M. and Milner, R. 1985. Algebraic laws for nondeterminism and concurrency.J. ACM 32, 1, 137–162. · Zbl 0629.68021 · doi:10.1145/2455.2460
[35] Hopf, E. 1954. The general temporally discrete Markoff process.J. Ration. Math. Mech. Anal. 3, 13–45. · Zbl 0055.36705
[36] Joyal, A., Nielsen, M., and Winskel, G. 1993. Bisimulation and open maps. InProceedings of 8th Annual IEEE Symposium on Logic in Computer Science. 418–427. · Zbl 0856.68067 · doi:10.1109/LICS.1993.287566
[37] Kim, C.-W. 1972. Approximation theorems for Markov operators.Prob. Theory Relat. Fields 21, 3, 207–214. · Zbl 0214.17004
[38] Kingman, J. F. C. and Taylor, S. J. 1966.Introduction to Measure and Probability. Cambridge University Press. · Zbl 0171.38603 · doi:10.1017/CBO9780511897214
[39] Kozen, D. 1985. A probabilistic PDL.J. Comput. Syst. Sci. 30, 2, 162–178. · Zbl 0575.03013 · doi:10.1016/0022-0000(85)90012-1
[40] Larsen, K. G. and Skou, A. 1991. Bisimulation through probablistic testing.Inf. Computat. 94, 1–28. · Zbl 0756.68035 · doi:10.1016/0890-5401(91)90030-6
[41] Mislove, M., Ouaknine, J., Pavlovic, D., and Worrell, J. 2004. Duality for labelled Markov processes. InFoundations of Software Science and Computation Structures (FOSSACS). I. Walukiewicz Ed., Lecture Notes in Computer Science, vol. 2987, 393–407. · Zbl 1126.68460 · doi:10.1007/978-3-540-24727-2_28
[42] Panangaden, P. 2009.Labelled Markov Processes. Imperial College Press. · Zbl 1190.60001 · doi:10.1142/p595
[43] Pavlovic, D., Mislove, M., and Worrell, J. B. 2006. Testing semantics: Connecting processes and process logics. InProceedings of the 11th International Conference on Algebraic Methodology and Software Technology (AMAST). Lecture Notes in Computer Science, vol. 4019, Springer-Verlag, 308–322. · Zbl 1236.68065
[44] Rudin, W. 1966.Real and Complex Analysis. McGraw-Hill. · Zbl 0142.01701
[45] Rutten, J. J. M. M. and de Vink, E. 1997. Bisimulation for probabilistic transition systems: a coalgebraic approach. InProceedings of ICALP’97. P. Degano Ed., Lecture Notes in Computer Science, vol. 1256, Springer-Verlag, 460–470. · Zbl 1401.68236
[46] Schaefer, H. H. 1974.Banach Lattices and Positive Operators. Springer-Verlag. · Zbl 0296.47023 · doi:10.1007/978-3-642-65970-6
[47] Selinger, P. 2004. Towards a semantics for higher-order quantum computation. InProceedings of the 2nd International Workshop on Quantum Programming Languages. 127–143. www.mathstat.dal.ca/ selinger/papers.htm.
[48] van Benthem, J. 1976. Modal correspondence theory. Ph.D. thesis, University of Amsterdam.
[49] van Breugel, F. and Worrell, J. 2001a. An algorithm for quantitative verification of probabilistic systems. InProceedings of the 12th International Conference on Concurrency Theory (CONCUR’01). K. G. Larsen and M. Nielsen Eds., Lecture Notes in Computer Science, vol. 2154, Springer-Verlag, 336–350. · Zbl 1006.68079
[50] van Breugel, F. and Worrell, J. 2001b. Towards quantitative verification of probabilistic systems. InProceedings of the 28th International Colloquium on Automata, Languages and Programming. Springer-Verlag. · Zbl 0986.68093
[51] van Breugel, F., Mislove, M., Ouaknine, J., and Worrell, J. 2003. An intrinsic characterization of approximate probabilistic bisimilarity. InProceedings of FOSSACS 03. Lecture Notes in Computer Science, vol. 2620, Springer-Verlag. · Zbl 1029.68112
[52] Vardi, M. 1985. Automatic verification of probabilistic concurrent finite-state programs. InProceedings of the 26th IEEE Symposium on Foundations of Computer Science. 327–338.
[53] Williams, D. 1991.Probability with Martingales. CUP, Cambridge. · Zbl 0722.60001 · doi:10.1017/CBO9780511813658
[54] Yosida, K. and Kakutani, S. 1941. Operator-theoretical treatment of Markoff’s process and mean ergodic theorem.Ann. Math. 42, 1, 188–228. · Zbl 0024.32402 · doi:10.2307/1968993
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.