[Prev][Next][Index][Thread]
Thesis: Discrete Approximation of Spaces
My thesis "Discrete Approximation of Spaces" is now available by
anonymous ftp from the site theory.doc.ic.ac.uk as file discrete.ps.Z
in the directory /papers/Suenderhauf/.
ABSTRACT.
In denotational semantics of higher programming languages, abstract
data types are represented by certain mathematical objects, the {\em
semantic domains.\/} For discrete datatypes such as {\tt integer} or
{\tt boolean}, and for higher types derived from these employing the
function space and product type constructors, this works fine in the
setting of domain theory. But for the datatype {\tt real} there is no
satisfying approach so far. This problem of finding a semantic domain
for the reals comes hand in hand with the question how to implement
the real line in a computer. This thesis gives an approach to solve
these problems.
The thesis may be divided into two parts. One part is concerned with
the problem of finding a good computational model of the real numbers,
the other part extends this construction to a fairly general class of
spaces and handles the type constructors `product' and `function
space'.
The computational model of the reals has the following salient
features. It is a countably based quasicontinuous domain which
contains a homeomorphic copy of the usual real line as its maximal
elements. The remaining elements are the {\em partial elements.\/}
They can be stratified into certain {\em levels of totality\/} each of
which can be seen as a discrete approximation of the real line. The
whole domain is constructed as a subspace of the upper power space of
the real line. Inside this rather huge domain we may view the real
numbers as represented by limits of partial elements. This order
theoretic limit process in the upper power space is replaced by an
internal operation which refers only to the discrete approximations.
This is achieved by equipping the latter with a certain
quasi-uniformity. The real numbers are then added by forming the {\em
completion\/} in the sense of quasi-uniform spaces. The partial
elements may be implemented as finite streams of digits, thought of as
parts of base-4-expansions of the respective numbers. The
quasi-uniformity on this set can be described in a finitary fashion:
It has a base consisting of relations $T_n$ such that $\alpha T_n
\beta$ may be decided by just inspecting the first~$n$ digits of the
sequences~$\alpha$ and~$\beta$.
The general construction is performed in the class of {\em uniformly
locally bounded quasi-uniform spaces.\/} As for the reals, models are
constructed as subsets of the power spaces. The choice of the
respective subsets is performed by specifying bases for the
quasi-uniformities. Again, the resulting models are stratified into
levels of totality which may be viewed as discrete approximants to the
respective spaces.
It is also possible to perform the constructions of product and
function space types on the side of the models. Hence we are able to
give models for spaces of all higher types which can be derived from
the real numbers.
---------
Philipp S{\"u}nderhauf
Fachbereich Mathematik (AG1)
Technische Hochschule Darmstadt
Schlo{\ss}gartenstr. 7 fax: x49-6151-164011
D-64289 Darmstadt email: sunderhauf@mathematik.th-darmstadt.de