Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Note on Reducibility Between Domain Representations

Speaker: Jens Blanck
Slot: Array, 10:50-11:10, col. 4


A notion of (continuous) reducibility of representations of
topological spaces is introduced and basic properties of this notion
is studied for domain representations.

A representation reduces to another if the representing map factors
through it. Reductions form a pre-order on representations. A
spectrum is a class of representations quoted by the equivalence
relation induced by reductions. The spectrum of dense domain
representations has a top element and representations within this
equivalence class are said to be admissible. The notion of
admissibility generalises the notion of admissibility in
TTE, and is stronger than the notion of admissibility used by
Hamrin. Admissible representations are of particular interest since
any continuous operation on the represented space can be represented.

Some domain representations of real numbers are considered and it is
shown that the usual interval domain representation, which is
admissible, does not reduce to a binary expansion domain
representation. However, a substructure of the interval domain more
suitable for efficient computation of operations are on the other
hand shown to be equivalent to the usual interval domain with
respect to reducibility.

websites: Arnold Beckmann 2006-04-20