Almost every domain is universal

Manfred Droste

(Universität Leipzig)

In classical results, Scott, Plotkin and others proved that
various classes of domains contain universal objects,
i.e. domains which contain any other domain of the given
class as a subdomain (up to isomorphism); such domains can
be used to provide models of the untyped \lambda-calculus.

We will present an inductive probabilistic construction
of bifinite domains and of Scott domains and show that
with probability 1 our construction produces a universal
bifinite domain resp. universal Scott-domain which, moreover,
has a large degree of symmetry. We also develop similar
probabilistic constructions for prime event structures and
for causal sets. The latter have been used as basic models
for discrete space-time in quantum gravity.

Joint work with Dietrich Kuske resp. Guo-Qiang Zhang.

Wednesday 3rd October 2007, 14:15
Board Room
Department of Computer Science