Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-19T07:18:53.816Z Has data issue: false hasContentIssue false
  • English
  • Français

A quantitative computational model for complete partial metric spaces via formal balls†

Published online by Cambridge University Press:  01 June 2009

SALVADOR ROMAGUERA  and
OSCAR VALERO
SALVADOR ROMAGUERA
Affiliation:
Instituto Universitario de Matemática Pura y Aplicada, Universidad Politécnica de Valencia, 46071 Valencia, Spain E-mail: [email protected]
OSCAR VALERO
Affiliation:
Departamento de Ciencias Matemáticas e Informática, Universidad de las Islas Baleares, 07122 Palma de Mallorca, Baleares, Spain E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Given a partial metric space (X, p), we use (BX, ⊑dp) to denote the poset of formal balls of the associated quasi-metric space (X, dp). We obtain characterisations of complete partial metric spaces and sup-separable complete partial metric spaces in terms of domain-theoretic properties of (BX, ⊑dp). In particular, we prove that a partial metric space (X, p) is complete if and only if the poset (BX, ⊑dp) is a domain. Furthermore, for any complete partial metric space (X, p), we construct a Smyth complete quasi-metric q on BX that extends the quasi-metric dp such that both the Scott topology and the partial order ⊑dp are induced by q. This is done using the partial quasi-metric concept recently introduced and discussed by H. P. Künzi, H. Pajoohesh and M. P. Schellekens (Künzi et al. 2006). Our approach, which is inspired by methods due to A. Edalat and R. Heckmann (Edalat and Heckmann 1998), generalises to partial metric spaces the constructions given by R. Heckmann (Heckmann 1999) and J. J. M. M. Rutten (Rutten 1998) for metric spaces.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 19 , Issue 3 , June 2009 , pp. 541 - 563
Copyright
Copyright © Cambridge University Press 2009

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

Aliakbari, M., Honari, B., Pourmahdian, M. and Rezaii, M. M. (2009) The space of formal balls and models of quasi-metric spaces. Mathematical Structures in Computer Science (to appear).Google Scholar
Edalat, A. (1995a) Domain theory and integration. Theoretical Computer Science 151 163–193.Google Scholar
Edalat, A. (1995b) Dynamical systems, measures and fractals via domain theory. Information and Computation 120 32–48.CrossRefGoogle Scholar
Edalat, A. and Heckmann, R. (1998) A computational model for metric spaces. Theoretical Computer Science 193 53–73.CrossRefGoogle Scholar
Edalat, A. and Sünderhauf, Ph. (1999) Computable Banach spaces via domain theory. Theoretical Computer Science 219 169–184.CrossRefGoogle Scholar
Engelking, R. (1977) General Topology, Monografie Mat. Tom 60, PWN-Polish Scientific Publishers.Google Scholar
Flagg, B. and Kopperman, R. (1997) Computational models for ultrametric spaces. Electronic Notes in Theoretical Computer Science 6 151–159.Google Scholar
Fletcher, P. and Lindgren, W. F. (1982) Quasi-Uniform Spaces, Marcel Dekker.Google Scholar
García-Raffi, L. M., Romaguera, S and Sánchez-Perez, E. A. (2002) Sequence spaces and asymmetric norms in the theory of computational complexity. Mathematical and Computer Modeling 36 1–11.Google Scholar
Gierz, G., Hofmann, K. H., Keimel, K., Lawson, J. D., Mislove, M. and Scott, D. S. (2003) Continuous Lattices and Domains, Encyclopedia of Mathematics and its Applications 93, Cambridge University Press.Google Scholar
Heckmann, R. (1999) Approximation of metric spaces by partial metric spaces. Applied Categorical Structures 7 71–83.CrossRefGoogle Scholar
Kopperman, K., Künzi, H. P. A. and Waszkiewicz, P. (2004) Bounded complete models of topological spaces. Topology and its Applications 139 285–297.Google Scholar
Krötzsch, M. (2006) Generalized ultrametric spaces in quantitative domain theory. Theoretical Computer Science 368 30–49.Google Scholar
Künzi, H. P. A. (1993) Nonsymmetric topology. In: Proc. Szekszárd Conf. 4, Bolyai Society of Math. Studies 303–338.Google Scholar
Künzi, H. P. A. (2001) Nonsymmetric distances and their associated topologies: About the origins of basic ideas in the area of asymmetric topology. In: Aull, C. E. and Lowen, R. (eds.) Handbook of the History of General Topology 3, Kluwer 853–968.Google Scholar
Künzi, H. P. A., Pajoohesh, H. and Schellekens, M. P. (2006) Partial quasi-metrics. Theoretical Computer Science 365 237–246.CrossRefGoogle Scholar
Künzi, H. P. A. and Schellekens, M. P. (2002) On the Yoneda completion of a quasi-metric spaces. Theoretical Computer Science 278 159–194.Google Scholar
Künzi, H. P. A. and Vajner, V. (1994) Weighted quasi-metric. In: Proceedings 8th Summer Conference% on General Topology and Applications. Ann. New York Acad. Sci. 728 64–77.Google Scholar
Lawson, J. (1997) Spaces of maximal points. Mathematical Structures in Computer Science 7 543–556.Google Scholar
Martin, K. (1998) Domain theoretic models of topological spaces. Electronic Notes in Theoretical Computer Science 13 173–181.Google Scholar
Martin, K. (2000) The measurament process in domain theory. In: Proceedings of the 27th ICALP. Springer-Verlag Lecture Notes in Computer Science 1853 116–126.CrossRefGoogle Scholar
Matthews, S. G. (1994) Partial metric topology. In: Procedings 8th Summer Conference on General Topology and Applications. Ann. New York Acad. Sci. 728 183–197.Google Scholar
Oltra, S., Romaguera, S. and Sánchez-Pérez, E. A. (2002) Bicompleting weightable quasi-metric spaces and partial metric spaces. Rendiconti del Circolo Matematico di Palermo 51 151–162.CrossRefGoogle Scholar
O'Neill, S. J. (1996) Partial metrics, valuations and domain theory. In: Proceedings 11th Summer Conference on General Topology and Applications. Ann. New York Acad. Sci. 806 304–315.Google Scholar
Reilly, I. L., Subrhamanyam, P. V. and Vamanamurthy, M. K. (1982) Cauchy sequences in quasi-pseudo-metric spaces. Monatshefte für Mathematik 93 127–140.Google Scholar
Romaguera, S. (1992) Left K-completeness in quasi-metric spaces. Mathematische Nachrichten 157 15–23.Google Scholar
Romaguera, S. and Sanchis, M. (2000) Semi-Lipschitz functions and best approximation in quasi-metric spaces. Journal of Approximation Theory 103 292–301.Google Scholar
Romaguera, S. and Sanchis, M. (2005) Properties of the normed cone of semi-Lipschitz functions. Acta Mathematica Hungarica 108 55–70.CrossRefGoogle Scholar
Romaguera, S. and Schellekens, M. P. (1999) Quasi-metric properties of complexity spaces. Topology and its Applications 98 311–322.Google Scholar
Romaguera, S. and Schellekens, M. P. (2005) Partial metric monoids and semivaluation spaces. Topology and its Applications 153 948–962.CrossRefGoogle Scholar
Rutten, J. J. M. M. (1998) Weighted colimits and formal balls in generalized metric spaces. Topology and its Applications 89 179–202.CrossRefGoogle Scholar
Schellekens, M. (1995) The Smyth completion: A common foundation for denotational semantics and complexity analysis. Electronic Notes in Theoretical Computer Science 1 535–556.CrossRefGoogle Scholar
Schellekens, M. P. (2003) A characterization of partial metrizability. Domains are quantifiable. Theoretical Computer Science 305 409–432.Google Scholar
Schellekens, M. P. (2004) The correspondence between partial metrics and semivaluations. Theoretical Computer Science 315 135–149.CrossRefGoogle Scholar
Smyth, M. B. (1988) Quasi-uniformities: Reconciling domains with metric spaces. In: Mathematical Foundations of Programming Language Semantics. Springer-Verlag Lecture Notes in Computer Science 298 236–253.Google Scholar
Smyth, M. B. (1991) Totally bounded spaces and compact ordered spaces as domains of computation. In: Reed, G. M., Roscoe, A. W. and Wachter, R. F. (eds.) Topology and Category Theory in Computer Science, Clarendon Press 207–229.Google Scholar
Sünderhauf, Ph. (1995) Quasi-uniform completeness in terms of Cauchy nets. Acta Mathematica Hungarica 69 47–54.Google Scholar
Waszkiewicz, P. (2001) Distance and measurement in domain theory. Electronic Notes in Theoretical Computer Science 45 448–462.Google Scholar
Waszkiewicz, P. (2003) Quantitative continuous domains. Applied Categorical Structures 11 41–67.CrossRefGoogle Scholar
Waszkiewicz, P. (2006) Partial metrisability of continuous posets. Mathematical Structures in Computer Science 16 359–372.Google Scholar