Quantitative Continuous Domains
by
Pawel Waszkiewicz
The University of Birmingham

Over recent years, a number of attempts have been made to equip domains used in semantic of programming languages with a notion of distance between points. Research in this area has led to a number of concepts which generalise the classical notion of a metric space to an ordered setting. In particular, partial metrics were introduced by Matthews [Mat92] and studied further by O'Neill [O'N95a, O'N95b].

More recently, Keye Martin introduced the idea of a measurement on a domain [Mar00]. At first glance, measurements are quite different from distance functions because they take only one argument. The original motivation of Martin was to make precise (in a quantitative way) the idea that elements at the top of a domain are totally specified whereas everything else is partial or an approximation. Consequently, he speaks of measuring the ``indefiniteness'' of a domain element, and seeks functions which assign zero exactly to the maximal elements. We call this requirement the kernel condition.

The first purpose of the talk is to explore the interplay between Martin's measurements and Matthew's partial metrics. The connection is very close: every partially metrized domain admits a measurement. On the other hand, under some mild assumptions, called stability, which we show to be necessary and sufficient, a standard construction from the theory of measurements can be used to define a partial metric compatible with the Scott topology on the domain.

Every partial metric gives rise to a metric in a standard way. Also, as we have said already, one can always derive a measurement from the partial metric, whenever the underlying set is a domain. Therefore, being equipped with a measurement, a partial metric and a metric, our quantitative domains can be regarded as ``three-level'' objects.

There are some computationally motivated restrictions on all three levels. Our basic requirement is that the partial metric topology agrees with the Scott topology on the domain. If this holds, we call the partial metric appropriate. In addition, we demand that the induced metric is complete and the derived measurement satisfies the kernel condition. It appears that this ideal situation is rare and we can only establish it for the class of continuous lattices.

Assuming just two of them, we get some interesting existence results.

We prove that:

• Every countably based algebraic domain which satisfies the Lawson condition [Law97] admits an appropriate partial metric and a measurement with the kernel condition.

Dropping the requirement on the measurement, we demonstrate that:

• Every countably based algebraic domain admits a partial metric such that the induced metric topology agrees with the Lawson topology. In this case, Lawson-compactness of the domain implies completeness of the induced metric.

Finally, generalising the last construction from algebraic to the continuous case, we show that:

• The induced metric topology may no longer agree with the Lawson topology but is complete whenever the domain is bounded-complete.

We discuss a number of examples and counterexamples to locate the strength of our results more exactly.

References:

[Law97] J. D. Lawson. Spaces of maximal points. Mathematical Structures in Computer Science, 7(5):543-555, October 1997.

[Mar00] K. Martin. A Foundation for Computation. PhD thesis, Department of Mathematics, Tulane University, New Orleans, LA 70118, 2000.

[Mat92] S. G. Matthews. Partial Metric Topology. In Proceedings of the 8th Summer Conference on Topology and Its Applications, volume 728, pages 176-185, 1992.

[O'N95a] S. J. O'Neill. Partial Metrics, Valuations and Domain Theory. Research Report CS-RR-293, Department of Computer Science, University of Warwick, Coventry, UK, October 1995.

[O'N95b] S. J. O'Neill. Two Topologies Are Better Than One. Research Report CS-RR-283, Department of Computer Science, University of Warwick, Coventry, UK, March 1995.

Date received: July 12, 2001