Logical Approaches to Computational Barriers

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 Weihrauch's 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 |