On Some Constructions in Quantitative Domain Theory
by
Dieter Spreen
University of Siegen

Domains introduced by Dana Scot and independently by Yuri L. Ershov are a structure modelling the notion of approximation and of computation. A computation performed using an algorithm proceeds in discrete steps. After each step there is more information available about the result of the computation. In this way the result obtained after each step can be seen as an approximation of the finite result.

Unlike in analytical mathematics, where natural metrics are at hand to measure the grade of an approximation, the theory of approximation based on domains was mainly of a qualitative nature. The situation started to change when M. B. Smyth discovered that there is a notion of distance in domains, but it is necessarily not symmetric. Similarly, S. Matthews found that canonical metrics defined for the maximal elements of certain domains can be extended to the whole domain by allowing that points may have a positive self-distance, which is considered as the weight of that point. He also showed that there is a close connection between a subclass of the quasi metrics used by Smyth and his partial metrics: each partial metric defines a weighted quasi metric and vice versa. In subsequent studies weights turned out to be a powerful tool for the introduction of partial metrics. A special class of weights are the measurements introduced by K. Martin in his thesis. They are strongly intertwined with the topological structure of a domain.

An obvious question raised independently by R. Heckmann and S. O'Neill is which domains are partial metrizable, i.e., on which domains exists a partial metric such that its topology coincides with the Scott topology of the domain. O'Neill showed that prime-algebraic Scott domains are partial metrizable. This result has recently been extended to the class of continuous domains with a countble basis, independently by M. Schellekens and P. Waszkiewicz.

It follows, of course, that also the product and, if it has a countable basis again, the space of all Scott continuous functions between such domains is partial metrizable, but if one constructs a partial metric on these domains by applying the definitions given in the above mentioned proofs one will not make use of the partial metrics coming with the components.

In this talk we study three important domain constructions, Cartesian products, function spaces and inverse limits of chains of domains with embedding/projection pairs as connecting morphisms, and show how a quasi metric and a measurement, respectively, for the composed spaces can be obtained from the corresponding maps coming with the components. The domains we consider are continuous directed-complete partial orders. In the case of the function space construction we also require the range space to be bounded-complete.

Date received: July 18, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cagx-45.