Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-18T06:49:47.227Z Has data issue: false hasContentIssue false
  • English
  • Français

Isomorphism theorems between models of mixed choice

Published online by Cambridge University Press:  28 December 2015

JEAN GOUBAULT-LARRECQ
JEAN GOUBAULT-LARRECQ*
Affiliation:
LSV, ENS Cachan, CNRS, INRIA Saclay, 61, avenue du président-Wilson, 94230 Cachan, France Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We relate the so-called powercone models of mixed non-deterministic and probabilistic choice proposed by Tix, Keimel, Plotkin, Mislove, Ouaknine, Worrell, Morgan and McIver, to our own models of previsions. Under suitable topological assumptions, we show that they are isomorphic. We rely on Keimel's cone-theoretic variants of the classical Hahn–Banach separation theorems, using functional analytic methods, and on the Schröder–Simpson Theorem.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 27 , Issue 6 , September 2017 , pp. 1032 - 1067
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abramsky, S. and Jung, A. (1994). Domain theory. In: Abramsky, S., Gabbay, D.M. and Maibaum, T.S.E. (eds.) Handbook of Logic in Computer Science, volume 3, Oxford University Press, 1–168.Google Scholar
Alvarez-Manilla, M., Jung, A. and Keimel, K. (2004). The probabilistic powerdomain for stably compact spaces. Theoretical Computer Science 328 (3) 221–244.Google Scholar
Edalat, A. (1995). Domain theory and integration. Theoretical Computer Science 151 (1) 163–193.Google Scholar
Ghani, N. and Uustalu, T. (2004). Coproducts of ideal monads. Theoretical Informatics and Applications 38 (4) 321–342.Google Scholar
Gierz, G., Hofmann, K.H., Keimel, K., Lawson, J.D., Mislove, M. and Scott, D.S. (2003). Continuous lattices and domains. In: Encyclopedia of Mathematics and its Applications, volume 93, Cambridge University Press.Google Scholar
Goubault-Larrecq, J. (2007). Continuous previsions. In: Duparc, J. and Henzinger, Th. A. (eds.) Proceedings of the 16th Annual EACSL Conference on Computer Science Logic (CSL'07), Lecture Notes in Computer Science, volume 4646, Lausanne, Switzerland, Springer, 542–557.Google Scholar
Goubault-Larrecq, J. (2008). Prevision domains and convex powercones. In: Amadio, R. (ed.) Proceedings of the 11th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'08), Lecture Notes in Computer Science, volume 4962, Budapest, Hungary, Springer, 318–333.Google Scholar
Goubault-Larrecq, J. (2010). De Groot duality and models of choice: Angels, demons, and nature. Mathematical Structures in Computer Science 20 (2) 169–237.CrossRefGoogle Scholar
Goubault-Larrecq, J. (2015a). A short proof of the Schröder-Simpson theorem. Mathematical Structures in Computer Science 25 (1) 1–5.Google Scholar
Goubault-Larrecq, J. (2015b). Full abstraction for non-deterministic and probabilistic extensions of PCF I: The angelic cases. Journal of Logic and Algebraic Methods in Programming 84 (1) 155–184.Google Scholar
Goubault-Larrecq, J. (2012b). QRB-domains and the probabilistic powerdomain. Logical Methods in Computer Science 8 (1:14) 1–33.Google Scholar
Heckmann, R. (1996). Spaces of valuations. In: Andima, S., Flagg, R. C., Itzkowitz, G., Kong, Y., Kopperman, R. and Misra, P. (eds.) Papers on General Topology and Applications: 11th Summer Conference at the University of Southern Maine, Annals of the New York Academy of Sciences 806, 174–200.Google Scholar
Jones, C. (1990). Probabilistic Non-Determinism, Ph.D. Thesis, University of Edinburgh. Technical Report ECS-LFCS-90-105.Google Scholar
Jung, A. (2004). Stably compact spaces and the probabilistic powerspace construction. In: Desharnais, J. and Panangaden, P. (eds.) Domain-theoretic Methods in Probabilistic Processes, Electronic Lecture Notes in Computer Science, volume 87, Elsevier. 15pp.Google Scholar
Keimel, K. (1984). Remarks on pointwise infima of lower semicontinuous functions. http://www.mathematik.tu-darmstadt.de/keimel/Papers/note84.pdf. Notes complementing the paper: Gerhard Gierz and Klaus Keimel, Halbstetige Funktionen und stetige Verbände, in Continuous Lattices and Related Topics, Mathematik Arbeitspapiere, 27 (1982), Universität Bremen 59–67.Google Scholar
Keimel, K. (2008). Topological cones: Functional analysis in a T 0-setting. Semigroup Forum 77 (1) 109–142.CrossRefGoogle Scholar
Keimel, K. (2012). Locally convex cones and the Schroeder-Simpson theorem. Quaestiones Mathematicae 35 (3) 353–390.CrossRefGoogle Scholar
Keimel, K. and Plotkin, G. (2009). Predicate transformers for convex powerdomains. Mathematical Structures in Computer Science 19 (3) 501–539.CrossRefGoogle Scholar
Keimel, K. and Plotkin, G. (2015). Mixed powerdomains for probability and nondeterminism. Logical Methods in Computer Science. To appear.Google Scholar
Kelley, J.L. (1955). General Topology, Van Nostrand Reinhold Co.Google Scholar
Kirch, O. (1993). Bereiche und Bewertungen, Master's thesis, Technische Hochschule Darmstadt.Google Scholar
Lüth, C. (1997). Categorical Term Rewriting: Monads and Modularity, Ph.D. thesis, University of Edinburgh.Google Scholar
McIver, A. and Morgan, C. (2001). Demonic, angelic and unbounded probabilistic choices in sequential programs. Acta Informatica 37 (4/5) 329–354.Google Scholar
Mislove, M. (1998). Topology, domain theory and theoretical computer science. Topology and Its Applications 89 (1–2) 3–59.Google Scholar
Mislove, M. (2000). Nondeterminism and probabilistic choice: Obeying the law. In: Proceedings of the 11th Conference on Concurrency Theory (CONCUR'00). Springer-Verlag Lecture Notes in Computer Science 1877 350–364.Google Scholar
Morgan, C., McIver, A. and Seidel, K. (1996). Probabilistic program transformers. ACM Transactions on Programming Languages and Systems 18 (3) 325–353.Google Scholar
Nachbin, L. (1965). Topology and Order, Van Nostrand, Princeton, NJ. Translated from the 1950 monograph “Topologia e Ordem” (in Portuguese). Reprinted by Robert E. Kreiger Publishing Co. Huntington, NY, 1967, 1976.Google Scholar
Schalk, A. (1993). Algebras for Generalized Power Constructions, Ph.D. thesis, Technische Universität Darmstadt.Google Scholar
Schröder, M. and Simpson, A. (2006). Probabilistic observations and valuations. In: Proceedings of the 21st Annual Conference on Mathematical Foundations of Programming Semantics (MFPS XXI). Electronic Notes in Computer Science 155 605–615, Elsevier.CrossRefGoogle Scholar
Schröder, M. and Simpson, A. (2009). Probabilistic observations and valuations. Invited talk at New Interactions between Analysis, Topology and Computation, Birmingham, UK. Slides available from http://homepages.inf.ed.ac.uk/als/Talks/birmingham09.pdf.Google Scholar
Tix, R. (1995). Stetige Bewertungen auf topologischen Räumen, Diplomarbeit, TH Darmstadt.Google Scholar
Tix, R. (1999). Continuous D-Cones: Convexity and Powerdomain Constructions, Ph.D. thesis, Technische Universität Darmstadt.Google Scholar
Tix, R., Keimel, K. and Plotkin, G. (2009). Semantic domains for combining probability and non-determinism. Electronic Notes in Theoretical Computer Science 222 3–99.Google Scholar
Varacca, D. (2002). The powerdomain of indexed valuations. In: Proceedings 17th Annual IEEE Symposium on Logic in Computer Science (LICS'02), Copenhagen. IEEE Computer Society Press, 299–308.Google Scholar
Varacca, D. (2003). Probability, Nondeterminism and Concurrency: Two Denotational Models for Probabilistic Computation, Ph.D. thesis, Dept. of Computer Science, U. Aarhus. BRICS Dissertation Series DS-03-14.Google Scholar
von Neumann, J. (1928). Zur Theorie der Gesellschaftspiele. Mathematische Annalen 100 295–320.Google Scholar