The probabilistic powerdomain for stably compact spaces. (English) Zbl 1071.68058
Summary: This paper reviews the one-to-one correspondence between stably compact spaces (a topological concept covering most classes of semantic domains) and compact ordered Hausdorff spaces. The correspondence is extended to certain classes of real-valued functions on these spaces. This is the basis for transferring methods and results from functional analysis to the non-Hausdorff setting.
As an application of this, the Riesz Representation Theorem is used for a straightforward proof of the (known) fact that every valuation on a stably compact space extends uniquely to a Radon measure on the Borel algebra of the corresponding compact Hausdorff space.
The view of valuations and measures as certain linear functionals on function spaces suggests considering a weak topology for the space of all valuations. If these are restricted to the probabilistic or sub-probabilistic case, then another stably compact space is obtained. The corresponding compact ordered space can be viewed as the set of (probability or sub-probability) measures together with their natural weak topology.
As an application of this, the Riesz Representation Theorem is used for a straightforward proof of the (known) fact that every valuation on a stably compact space extends uniquely to a Radon measure on the Borel algebra of the corresponding compact Hausdorff space.
The view of valuations and measures as certain linear functionals on function spaces suggests considering a weak topology for the space of all valuations. If these are restricted to the probabilistic or sub-probabilistic case, then another stably compact space is obtained. The corresponding compact ordered space can be viewed as the set of (probability or sub-probability) measures together with their natural weak topology.
MSC:
| 68Q55 | Semantics in the theory of computing |
References:
| [1] | Abramsky, S., Domain theory in logical form, Ann. Pure Applied Logic, 51, 1-77 (1991) · Zbl 0737.03006 |
| [2] | Abramsky, S.; Jung, A., Domain theory, (Abramsky, S.; Gabbay, D. M.; Maibaum, T. S.E., Handbook of Logic in Computer Science, Vol. 3 (1994), Clarendon Press: Clarendon Press Oxford), 1-68 · Zbl 0829.68111 |
| [3] | M. Alvarez-Manilla, Measure theoretic results for continuous valuations on partially ordered spaces, Ph.D. thesis, Imperial College, University of London, 2001.; M. Alvarez-Manilla, Measure theoretic results for continuous valuations on partially ordered spaces, Ph.D. thesis, Imperial College, University of London, 2001. |
| [4] | Alvarez-Manilla, M.; Edalat, A.; Saheb-Djahromi, N., An extension result for continuous valuations, J. London Math. Soc., 61, 629-640 (2000) · Zbl 0960.60005 |
| [5] | G. Birkhoff, Lattice Theory, 3rd Edition, AMS Colloq. Publication, Vol. 25, American Mathematical Society, Providence, 1967.; G. Birkhoff, Lattice Theory, 3rd Edition, AMS Colloq. Publication, Vol. 25, American Mathematical Society, Providence, 1967. · Zbl 0153.02501 |
| [6] | Choquet, G., Theory of capacities, Ann. Inst. Fourier, Grenoble, 5, 131-296 (1953) · Zbl 0064.35101 |
| [7] | Choquet, G., Lectures on Analysis, Vol. 2 (1969), W. A. Benjamin Inc.: W. A. Benjamin Inc. London · Zbl 0181.39602 |
| [8] | Desharnais, J.; Gupta, V.; Jagadeesan, R.; Panangaden, P., Metrics for labeled Markov systems, (Baeten, J. C.M.; Mauw, S., Proc. 10th Internat. Conf. on Concurrency Theory, Lecture Notes in Computer Science, Vol. 1664 (1999), Springer: Springer Berlin), 258-273 · Zbl 0939.68081 |
| [9] | Edwards, D. A., On the existence of probability measures with given marginals, Ann. Inst. Fourier, Grenoble,, 28, 53-78 (1978) · Zbl 0377.60004 |
| [10] | Gierz, G.; Hofmann, K. H.; Keimel, K.; Lawson, J. D.; Mislove, M.; Scott, D. S., A Compendium of Continuous Lattices (1980), Springer: Springer Berlin · Zbl 0452.06001 |
| [11] | Gierz, G.; Hofmann, K. H.; Keimel, K.; Lawson, J. D.; Mislove, M.; Scott, D. S., Continuous Lattices and Domains, Encyclopedia of Mathematics and its Applications, Vol. 93 (2003), Cambridge University Press: Cambridge University Press Cambridge, (Revised and expanded edition of \([ \operatorname{GHK}^+ 80])\) · Zbl 1088.06001 |
| [12] | Hofmann, K. H., Stably continuous frames and their topological manifestations, (Bentley, H. L.; Herrlich, H.; Rajagopalan, M.; Wolff, H., Categorical Topology, Proc. 1983 Conf. Toledo, Sigma Series in Pure and Applied Mathematics, Vol. 5 (1984), Heldermann: Heldermann Berlin), 282-307 · Zbl 0552.06005 |
| [13] | Horn, A.; Tarski, A., Measures on Boolean algebras, Trans. Amer. Math. Soc., 64, 467-497 (1948) · Zbl 0035.03001 |
| [14] | C. Jones, Probabilistic non-determinism, Ph.D. thesis, University of Edinburgh, Edinburgh, 1990. Also published as Technical Report No. CST-63-90.; C. Jones, Probabilistic non-determinism, Ph.D. thesis, University of Edinburgh, Edinburgh, 1990. Also published as Technical Report No. CST-63-90. |
| [15] | Jones, C.; Plotkin, G., A probabilistic powerdomain of evaluations, (Proc. 4th Annu. Symp. on Logic in Computer Science (1989), IEEE Computer Society Press), 186-195 · Zbl 0716.06003 |
| [16] | A. Jung, Cartesian Closed Categories of Domains, CWI Tracts, Vol. 66, Centrum voor Wiskunde en Informatica, Amsterdam, 1989. 107 pp.; A. Jung, Cartesian Closed Categories of Domains, CWI Tracts, Vol. 66, Centrum voor Wiskunde en Informatica, Amsterdam, 1989. 107 pp. · Zbl 0719.06004 |
| [17] | Jung, A., The classification of continuous domains, (Proc. 5th Annu. IEEE Symp. Logic in Computer Science (1990), IEEE Computer Society Press: IEEE Computer Society Press Silverspring, MD), 35-40 · Zbl 0825.68599 |
| [18] | Jung, A., Stably compact spaces and the probabilistic powerspace construction, (Desharnais, J.; Panangaden, P., Proc. Workshop on Domain-theoretic Methods in Probabilistic Processes, Electronic Notes in Theoretical Computer Science, Vol. 87 (2004), Elsevier Science Publishers B.V.: Elsevier Science Publishers B.V. Amsterdam) · Zbl 1270.68152 |
| [19] | Jung, A.; Tix, R., The troublesome probabilistic powerdomain, (Edalat, A.; Jung, A.; Keimel, K.; Kwiatkowska, M., Proc. 3rd Workshop on Computation and Approximation, Electronic Notes in Theoretical Computer Science, Vol. 13 (1998), Elsevier Science Publishers B.V.: Elsevier Science Publishers B.V. Amsterdam), 23 pages · Zbl 0917.68135 |
| [20] | M. Kegelmann, Continuous domains in logical form, Ph.D. thesis, School of Computer Science, The University of Birmingham, 1999.; M. Kegelmann, Continuous domains in logical form, Ph.D. thesis, School of Computer Science, The University of Birmingham, 1999. · Zbl 1080.03043 |
| [21] | Keimel, K., The probabilistic powerdomain for the upwards topology of compact ordered spaces, (Desharnais, J.; Panangaden, P., Proc. Workshop on Domain-theoretic Methods in Probabilistic Processes, Electronic Notes in Theoretical Computer Science, Vol. 87 (2004), Elsevier Science Publishers B.V.: Elsevier Science Publishers B.V. Amsterdam) · Zbl 1276.54041 |
| [22] | O. Kirch, Bereiche und Bewertungen. Master’s thesis, Technische Hochschule Darmstadt, June 1993, 77pp.; O. Kirch, Bereiche und Bewertungen. Master’s thesis, Technische Hochschule Darmstadt, June 1993, 77pp. |
| [23] | König, H., Measure and Integration (1997), Springer: Springer Berlin · Zbl 0887.28001 |
| [24] | Kozen, D., Semantics of probabilistic programs, J. Comput. System Sci., 22, 328-350 (1981) · Zbl 0476.68019 |
| [25] | Lawson, J. D., Valuations on continuous lattices, (Hoffmann, R. E., Continuous Lattices and Related Topics, Mathematik Arbeitspapiere, Vol. 27 (1982), Universität Bremen), 204-225 |
| [26] | Lawson, J. D., The versatile continuous order, (Main, M.; Melton, A.; Mislove, M.; Schmidt, D., Mathematical Foundations of Programming Language Semantics, Lecture Notes in Computer Science, Vol. 298 (1988), Springer: Springer Berlin), 134-160 · Zbl 0662.06002 |
| [27] | J. D. Lawson, Domains, integration, and “positive analysis”, Math. Structures Comput. Sci., to appear.; J. D. Lawson, Domains, integration, and “positive analysis”, Math. Structures Comput. Sci., to appear. · Zbl 1083.03055 |
| [28] | Moshier, M. A.; Jung, A., A logic for probabilities in semantics, (Bradfield, J., Computer Science Logic, Lecture Notes in Computer Science, Vol. 2471 (2002), Springer: Springer Berlin), 216-231 · Zbl 1020.68050 |
| [29] | L. Nachbin, Topology and Order, Von Nostrand, Princeton, N.J., 1965. Translated from the 1950 monograph “Topologia e Ordem” (in Portugese). Reprinted by Robert E. Kreiger Publishing Co., Huntington, NY, 1967.; L. Nachbin, Topology and Order, Von Nostrand, Princeton, N.J., 1965. Translated from the 1950 monograph “Topologia e Ordem” (in Portugese). Reprinted by Robert E. Kreiger Publishing Co., Huntington, NY, 1967. |
| [30] | Pettis, B. J., On the extension of measures, Ann. Math., 54, 1, 186-197 (1951) · Zbl 0043.27903 |
| [31] | Saheb-Djahromi, N., CPO’s of measures for nondeterminism, Theoret. Comput. Sci., 12, 19-37 (1980) · Zbl 0433.68017 |
| [32] | Scott, D. S., Outline of a mathematical theory of computation, (4th Ann. Princeton Conf. Information Sciences and Systems (1970)), 169-176 |
| [33] | Scott, D. S., Domains for denotational semantics, (Nielson, M.; Schmidt, E. M., International Colloquium on Automata, Languages and Programs, Lecture Notes in Computer Science, Vol. 140 (1982), Springer: Springer Berlin), 577-613 · Zbl 0495.68025 |
| [34] | Smyth, M. B., Powerdomains and predicate transformersa topological view, (Diaz, J., Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 154 (1983), Springer: Springer Berlin), 662-675 · Zbl 0533.68018 |
| [35] | Smyth, M. B., Topology, (Abramsky, S.; Gabbay, D. M.; Maibaum, T. S.E., Handbook of Logic in Computer Science, Vol. 1 (1992), Clarendon Press: Clarendon Press Oxford), 641-761 · Zbl 0777.68001 |
| [36] | R. Tix, Stetige Bewertungen auf topologischen Räumen, Master’s thesis, Technische Hochschule Darmstadt, June 1995, 51pp.; R. Tix, Stetige Bewertungen auf topologischen Räumen, Master’s thesis, Technische Hochschule Darmstadt, June 1995, 51pp. |
| [37] | Topsøe, F., Topology and Measure, (Lecture Notes in Mathematics, Vol. 133 (1970), Springer: Springer Berlin) · Zbl 0197.33301 |
| [38] | Vickers, S. J., Cambridge Tracts in Theoretical Computer Science, Vol. 5 (1989), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0668.54001 |
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.
