Abstract
We define strong monads of continuous (lower, upper) previsions, and of forks, modeling both probabilistic and non-deterministic choice. This is an elegant alternative to recent proposals by Mislove, Tix, Keimel, and Plotkin. We show that our monads are sound and complete, in the sense that they model exactly the interaction between probabilistic and (demonic, angelic, chaotic) choice.
Partially supported by the INRIA ARC ProNoBis. Part of Section was done while the author was invited at U. Laval, Québec City, Québec, July 2004. We acknowledge their support.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abramsky, S., Jung, A.: Domain theory. In: Abramsky, S., Gabbay, D.M., Maibaum, T.S.E. (eds.) Handbook of Logic in Computer Science, vol. 3, pp. 1–168. Oxford University Press, Oxford (1994)
Ghani, N., Uustalu, T.: Coproducts of ideal monads. Theoretical Informatics and Applications 38(4), 321–342 (2004)
Gierz, G., Hofmann, K.H., Keimel, K., Lawson, J.D., Mislove, M., Scott, D.S.: Continuous lattices and domains. In: Encyclopedia of Mathematics and its Applications, vol. 93, Cambridge University Press, Cambridge (2003)
Gilboa, I., Schmeidler, D.: Additive representation of non-additive measures and the Choquet integral. Discussion Papers 985, Northwestern University, Center for Mathematical Studies in Economics and Management Science (1992)
Goubault-Larrecq, J.: Continuous capacities on continuous state spaces. In: Arge, L., Cachin, C., Jurdzinski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 764–776. Springer, Heidelberg (2007)
Goubault-Larrecq, J.: Une introduction aux capacités, aux jeux et aux prévisions. Version 1.7 (June 2007), http://www.lsv.ens-cachan.fr/~goubault/ProNobis/pp.pdf
Jones, C.: Probabilistic Non-Determinism. PhD thesis, University of Edinburgh, Technical Report ECS-LFCS-90-105 (1990)
Jung, A.: Stably compact spaces and the probabilistic powerspace construction. In: Desharnais, J., Panangaden, P. (eds.) Domain-theoretic Methods in Probabilistic Processes. Electronic Lecture Notes in Computer Science, vol. 87, p. 15. Elsevier, Amsterdam (2004)
Keimel, K., Plotkin, G.: Predicate transformers for convex powerdomains. Math. Struct. Comp. Sci., p. 42 (submitted 2007)
Max Kelly, G.: A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves and so on. Bull. Austr. Math. Soc. 22, 1–83 (1980)
Lüth, C.: Categorical Term Rewriting: Monads and Modularity. PhD thesis, University of Edinburgh (1997)
Maaß, S.: Coherent lower previsions as exact functionals and their (sigma-)core. In: de Cooman, G., Fine, T., Seidenfeld, T. (eds.) Proc. 2nd Intl. Symp. Imprecise Probabilities and their Applications (ISIPTA 2001), pp. 230–236 (2001)
Maass, S.: Continuous linear representation of coherent lower previsions. In: Bernard, J.-M., Seidenfeld, T., Zaffalon, M. (eds.) Proc. 3rd Intl. Symp. on Imprecise Probabilities and Their Applications (ISIPTA 2003), Carleton Sci. Proc. in Informatics, vol. 18, pp. 371–381 (2003)
Manes, E.G.: Algebraic Theories. Graduate Texts in Mathematics, vol. 26. Springer, Heidelberg (1976)
Mislove, M.: Topology, domain theory and theoretical computer science. Topology and Its Applications 89, 3–59 (1998)
Mislove, M.: Nondeterminism and probabilistic choice: Obeying the law. In: Palamidessi, C. (ed.) CONCUR 2000. LNCS, vol. 1877, pp. 350–364. Springer, Heidelberg (2000)
Moggi, E.: Notions of computation and monads. Inf. & Comp. 93, 55–92 (1991)
Osborne, M.J., Rubinstein, A.: A Course in Game Theory. MIT Press, Cambridge (1994)
Plotkin, G.: A domain-theoretic Banach-Alaoglu theorem. Math. Struct. Comp. Sci. 16, 299–311 (2006)
Ramsey, N., Pfeffer, A.: Stochastic lambda calculus and monads of probability distributions. In: Proc. 29th Ann. ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages (POPL 2002), pp. 154–165 (2002)
Roth, W.: Hahn-Banach type theorems for locally convex cones. Journal of the Australian Mathematical Society 68(1), 104–125 (2000)
Tix, R.: Stetige Bewertungen auf topologischen Räumen. Diplomarbeit, TH Darmstadt (June 1995)
Tix, R.: Continuous D-Cones: Convexity and Powerdomain Constructions. PhD thesis, Technische Universität Darmstadt (1999)
Tix, R., Keimel, K., Plotkin, G.: Semantic domains for combining probability and non-determinism. Electronic Notes in Theoretical Computer Science 129, 1–104 (2005)
Varacca, D.: The powerdomain of indexed valuations. In: Proc. 17th Ann. Symp. Logic in Computer Science (LICS 2002), pp. 299–308. IEEE Computer Society Press, Los Alamitos (2002)
Varacca, D., Winskel, G.: Distributing probability over nondeterminism. Math. Struct. Comp. Sci., 26 (accepted 2005)
Wadler, P.: Comprehending monads. Math. Struct. Comp. Sci. 2, 461–493 (1992)
Walley, P.: Statistical Reasoning with Imprecise Probabilities. Chapman and Hall, London (1991)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goubault-Larrecq, J. (2007). Continuous Previsions. In: Duparc, J., Henzinger, T.A. (eds) Computer Science Logic. CSL 2007. Lecture Notes in Computer Science, vol 4646. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74915-8_40
Download citation
DOI: https://doi.org/10.1007/978-3-540-74915-8_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74914-1
Online ISBN: 978-3-540-74915-8
eBook Packages: Computer ScienceComputer Science (R0)