Computability in Europe 2006
Logical Approaches to Computational Barriers
|Slot:||Mon, 10:50-11:10, Faraday D (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||
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie06/conf-code.php on line 135