On the computational content of the Lawson topology

DOI10.1016/J.TCS.2006.03.021MaRDI QIDQ2500493zbMATH OpenOpenAlexFDO

Authors Frédéric De Jaeger, Martín Escardo, Gabriele Santini

Publication date 16 August 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.03.021

zbMATH Keywords

computability in Euclidean spacecomputable compact setcomputable real numbereffectively given domainsLawson topologyScott topologyVietoris topology

Mathematics Subject Classification ID

Theory of numerations, effectively presented structures (03D45) Constructive and recursive analysis (03F60) Continuous lattices and posets, applications (06B35) Linearly ordered topological spaces, generalized ordered spaces, and partially ordered spaces (54F05)

Review text

We quote the well-written abstract almost verbatim: An element of an effectively given domain is computable if and only if 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 neighborhoods 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 if and only if it is a recursively enumerable set, and it is Lawson computable precisely when 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 proposed by \textit{V. Brattka} and \textit{K. Weihrauch} [Theor. Comput. Sci. 219, 65--93 (1999; Zbl 0916.68042)] in the framework of type-two recursion theory.

Recommendations

• scientific article; zbMATH DE number 3849214
• Effectively enumerable topological spaces
• Real number computability and domain theory
• Elementary computable topology
• On effective topological spaces

Cites work

• Computability on subsets of Euclidean space. I: Closed and compact subsets
• Continuous Lattices and Domains
• Data Types as Lattices
• Effectively given domains
• scientific article; zbMATH DE number 4081629 (Why is no real title available?)
• scientific article; zbMATH DE number 3706504 (Why is no real title available?)
• scientific article; zbMATH DE number 41225 (Why is no real title available?)
• scientific article; zbMATH DE number 108365 (Why is no real title available?)
• scientific article; zbMATH DE number 1229489 (Why is no real title available?)
• scientific article; zbMATH DE number 1231645 (Why is no real title available?)
• scientific article; zbMATH DE number 1330441 (Why is no real title available?)
• scientific article; zbMATH DE number 1948164 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 783754 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Spaces of maximal points
• Stably compact spaces and closed relations
• The probabilistic powerdomain for stably compact spaces
• The regular-locally compact coreflection of a stably locally compact locale
• Topology, domain theory and theoretical computer science

Cited in

(3)

• scientific article; zbMATH DE number 3849214 (Why is no real title available?)
• scientific article; zbMATH DE number 7471696 (Why is no real title available?)
• Lawson topology of the space of formal balls and the hyperbolic topology

This page was built for publication: On the computational content of the Lawson topology

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500493)