A computational model for metric spaces. (English) Zbl 1011.54026
Summary: For every metric space \(X\), we define a continuous poset \(BX\) such that \(X\) is homeomorphic to the set of maximal elements of \(BX\) with the relative Scott topology. The poset \(BX\) is a dcpo iff \(X\) is complete, and \(\omega\)-continuous iff \(X\) is separable. The computational model \(BX\) is used to give domain-theoretic proofs of Banach’s fixed point theorem and of two classical results of Hutchinson: on a complete metric space, every hyperbolic iterated function system has a unique non-empty compact attractor, and every iterated function system with probabilities has a unique invariant measure with bounded support. We also show that the probabilistic power domain of \(BX\) provides an \(\omega\)-continuous computational model for measure theory on a separable complete metric space \(X\).
MSC:
| 54E35 | Metric spaces, metrizability |
| 06B35 | Continuous lattices and posets, applications |
| 54F05 | Linearly ordered topological spaces, generalized ordered spaces, and partially ordered spaces |
| 28C15 | Set functions and measures on topological spaces (regularity of measures, etc.) |
| 54E40 | Special maps on metric spaces |
References:
| [1] | Abramsky, S.; Jung, A., Domain theory, (Abramsky, S.; Gabbay, D. M.; Maibaum, T. S.E., Handbook of Logic in Computer Science, Vol. III (1994), Oxford Univ. Press: Oxford Univ. Press Oxford) · Zbl 0829.68111 |
| [2] | Edalat, A., Continuous information categories, (Tech. Report Doc 91/41 (1991), Imperial College) · Zbl 0977.18500 |
| [3] | Edalat, A., Domain theory and integration, Theoret. Comput. Sci., 151, 163-193 (1995) · Zbl 0872.28006 |
| [4] | Edalat, A., Dynamical systems, measures and fractals via domain theory, Inform. Comput., 120, 32-48 (1995) · Zbl 0834.58029 |
| [5] | Edalat, A., Power domains and iterated function systems, Inform. Comput., 124, 182-197 (1996) · Zbl 0916.54014 |
| [6] | Edalat, A., The Scott topology induces the weak topology, (LICS ’96 (1996), IEEE Computer Soc. Press: IEEE Computer Soc. Press Silver Spring, MD) |
| [7] | Federer, H., Geometric Measure Theory (1969), Springer-Verlag: Springer-Verlag Berlin · Zbl 0176.00801 |
| [8] | Hayashi, S., Self-similar sets as Tarski’s fixed points, Publ. Res. Inst. Math. Sci., 21, 1059-1066 (1985) · Zbl 0618.54030 |
| [9] | Hutchinson, J. E., Fractals and self-similarity, Indiana Univ. Math. J., 30, 713-747 (1981) · Zbl 0598.28011 |
| [10] | Jones, C. J., Probabilistic non-determinism, (Ph.D. Thesis (1990), Univ. of Edinburgh) |
| [11] | Jones, C. J.; Plotkin, G. D., A probabilistic powerdomain of evaluations, (LICS ’89 (1989), IEEE Computer Soc. Press: IEEE Computer Soc. Press Silver Spring, MD), 186-195 · Zbl 0716.06003 |
| [12] | Kamimura, T.; Tang, A., Total objects of domains, Theoret. Comput. Sci., 34, 275-288 (1984) · Zbl 0551.68047 |
| [13] | Lawson, J. D., Valuations on continuous lattices, (Hoffmann, R.-E., Continuous Lattices and Related Topics. Continuous Lattices and Related Topics, Mathematik Arbeitspapiere, Vol. 27 (1982), Universität Bremen) · Zbl 0195.03304 |
| [14] | Lawson, J. D., Maximal valuations in MP hulls (1995), personal communication |
| [15] | J.D. Lawson, Spaces of maximal points, Math. Struct. Comput. Sci.; J.D. Lawson, Spaces of maximal points, Math. Struct. Comput. Sci. · Zbl 0985.54025 |
| [16] | Norberg, T., Existence theorems for measures on continuous posets, with applications to random set theory, Math. Scand., 64, 15-51 (1989) · Zbl 0667.60001 |
| [17] | Weihrauch, K.; Schreiber, U., Embedding metric spaces into cpo’s, Theoret. Comput. Sci., 16, 5-24 (1981) · Zbl 0485.68040 |
| [18] | Zhang, H., Dualities of domains, (Ph.D. Thesis (1993), Department of Mathematics, Tulane University) |
| [19] | Blanck, J., Domain representability of metric spaces, Annals of Pure and Applied Logic (1997), to appear. · Zbl 0867.03014 |
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.
