On the computational content of the Lawson topology

Research output: Contribution to journalArticle

Standard

On the computational content of the Lawson topology. / De Jaeger, F; Escardo, Martin; Santini, G.

In: Theoretical Computer Science, Vol. 357, No. 1-3, 25.07.2006, p. 230-240.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

De Jaeger, F ; Escardo, Martin ; Santini, G. / On the computational content of the Lawson topology. In: Theoretical Computer Science. 2006 ; Vol. 357, No. 1-3. pp. 230-240.

Bibtex

@article{7cd07a577a53409792b638a6847fda7c,
title = "On the computational content of the Lawson topology",
abstract = "An element of an effectively given domain is computable iff its basic Scott open neighbourhoods are recursively enumerable. We thus refer to computable elements as Scott computable and define an element to be Lawson computable if its basic Lawson open neighbourhoods are recursively enumerable. Since the Lawson topology is finer than the Scott topology, a stronger notion of computability is obtained. For example, in the powerset of the natural numbers with its standard effective presentation, an element is Scott computable iff it is a recursively enumerable set, and it is Lawson computable iff it is a recursive set. Among other examples, we consider the upper powerdomain of Euclidean space, for which we prove that Scott and Lawson computability coincide with two notions of computability for compact sets recently proposed by Brattka and Weihrauch in the framework of type-two recursion theory. (C) 2006 Elsevier B.V. All rights reserved.",
keywords = "effectively given domains, Scott topology, computability in Euclidean space, power, computable compact set, computable real number, Lawson topology, Vietoris topology",
author = "{De Jaeger}, F and Martin Escardo and G Santini",
year = "2006",
month = jul,
day = "25",
doi = "10.1016/j.tcs.2006.03.021",
language = "English",
volume = "357",
pages = "230--240",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1-3",

}

RIS

TY - JOUR

T1 - On the computational content of the Lawson topology

AU - De Jaeger, F

AU - Escardo, Martin

AU - Santini, G

PY - 2006/7/25

Y1 - 2006/7/25

N2 - An element of an effectively given domain is computable iff its basic Scott open neighbourhoods are recursively enumerable. We thus refer to computable elements as Scott computable and define an element to be Lawson computable if its basic Lawson open neighbourhoods are recursively enumerable. Since the Lawson topology is finer than the Scott topology, a stronger notion of computability is obtained. For example, in the powerset of the natural numbers with its standard effective presentation, an element is Scott computable iff it is a recursively enumerable set, and it is Lawson computable iff it is a recursive set. Among other examples, we consider the upper powerdomain of Euclidean space, for which we prove that Scott and Lawson computability coincide with two notions of computability for compact sets recently proposed by Brattka and Weihrauch in the framework of type-two recursion theory. (C) 2006 Elsevier B.V. All rights reserved.

AB - An element of an effectively given domain is computable iff its basic Scott open neighbourhoods are recursively enumerable. We thus refer to computable elements as Scott computable and define an element to be Lawson computable if its basic Lawson open neighbourhoods are recursively enumerable. Since the Lawson topology is finer than the Scott topology, a stronger notion of computability is obtained. For example, in the powerset of the natural numbers with its standard effective presentation, an element is Scott computable iff it is a recursively enumerable set, and it is Lawson computable iff it is a recursive set. Among other examples, we consider the upper powerdomain of Euclidean space, for which we prove that Scott and Lawson computability coincide with two notions of computability for compact sets recently proposed by Brattka and Weihrauch in the framework of type-two recursion theory. (C) 2006 Elsevier B.V. All rights reserved.

KW - effectively given domains

KW - Scott topology

KW - computability in Euclidean space

KW - power

KW - computable compact set

KW - computable real number

KW - Lawson topology

KW - Vietoris topology

UR - http://www.scopus.com/inward/record.url?scp=33745336481&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2006.03.021

DO - 10.1016/j.tcs.2006.03.021

M3 - Article

VL - 357

SP - 230

EP - 240

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1-3

ER -