Computable Real-Valued Functions on Recursive Open and Closed Subsets of Euclidean Space

In this paper we study intrinsic notions of “computability” for open and closed subsets of Euclidean space. Here we combine together the two concepts, computability on abstract metric spaces and computability for continuous functions, and delineate the basic properties of computable open and closed sets. The paper concludes with a comprehensive examination of the Effective Riemann Mapping Theorem and related questions.     

The discrete parts of approximately decidable sets in Euclidean spaces

It is shown that the classes of discrete parts, A ∩ ?^k, of approximately resp. weakly decidable subsets of Euclidean spaces, A ? ?^k, coincide and are equal to the class of ω‐r. e. sets which is well‐known as the first transfinite level in Ershov's hierarchy exhausting Δ⁰₂.     

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

The topological arithmetical hierarchy is the effective version of the Borel hierarchy. Its class Δ^ta₂ is just large enough to include several types of pointsets in Euclidean spaces ℝ^k which are fundamental in computable analysis. As a crossbreed of Hausdorff's difference hierarchy in the Borel class Δ^B₂ and Ershov's hierarchy in the class Δ⁰₂ of the arithmetical hierarchy, the Hausdorff-Ershov hierarchy introduced in this paper gives a powerful classification within Δ^ta₂. This is based on suitable characterizations of the sets from Δ^ta₂ which are obtained in a close analogy to those of the Δ^B₂ sets as well as those of the Δ⁰₂ sets. A helpful tool in dealing with resolvable sets is contributed by the technique of depth analysis. On this basis, the hierarchy properties, in particular the strict inclusions between classes of different levels, can be shown by direct constructions of witness sets. The Hausdorff-Ershov hierarchy runs properly over all constructive ordinals, in contrast to Ershov's hierarchy whose denotation-independent version collapses at level ω². Also, some new characterizations of concepts of decidability for pointsets in Euclidean spaces are presented.     

Sobriety in Terms of Nets

Sobriety is a subtle notion of completeness for topological spaces: A space is sober if it may be reconstructed from the lattice of its open subsets. The usual criterion to check sobriety involves either irreducible closed subsets or completely prime filters of open sets. This paper provides an alternative possibility, thus trying to make sobriety easier to understand. We define the notion of observative net, which, together with an appropriate convergence notion, characterizes sobriety. As the filter approach does not involve just usual (topological) convergence, this is not an instance of the classical net-filter translation in general topology.     

Local paraconvexity and local selection theorems

Theorems on the local extendability of selections for non-convex-valued maps of paracompact spaces into Banach spaces, i.e., infinite-dimensional analogs of the finite-dimensional Michael selection theorem are proved. We were able to obtain these results under an appropriate metric control of the local degree of nonconvexity on the valuesF(x), which naturally leads us to introduce the notion of equi-locally paraconvex families of sets. It is shown that all convex subsets of the integral curves of the differential equationy′=f(x,y) with a continuous right-hand sidef and the isometric images of such subsets form an equi-locally paraconvex family of subsets of a Euclidean space. Translated fromMatematicheskie Zametki, Vol. 65, No. 2, pp. 261–269, February, 1999.     

Uniform domain representations of ℓp ‐spaces

The category of Scott‐domains gives a computability theory for possibly uncountable topological spaces, via representations. In particular, every separable Banach‐space is representable over a separable domain. A large class of topological spaces, including all Banach‐spaces, is representable by domains, and in domain theory, there is a well‐understood notion of parametrizations over a domain. We explore the link with parameter‐dependent collections of spaces in e. g. functional analysis through a case study of ?^p ‐spaces. We show that a well‐known domain representation of ?^p as a metric space can be made uniform in the sense of parametrizations of domains. The uniform representations admit lifting of continuous functions and are effective in p. Dependent type constructions apply, and through the study of the sum and product spaces, we clarify the notions of uniformity and uniform computability. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Normal cone approximation and offset shape isotopy

This work addresses the problem of the approximation of the normals of the offsets of general compact sets in Euclidean spaces. It is proven that for general sampling conditions, it is possible to approximate the gradient vector field of the distance to general compact sets. These conditions involve the μ-reach of the compact set, a recently introduced notion of feature size. As a consequence, we provide a sampling condition that is sufficient to ensure the correctness up to isotopy of a reconstruction given by an offset of the sampling. We also provide a notion of normal cone to general compact sets that is stable under perturbation.     

Dense computability structures

We examine computability structures on a metric space and the relationships between maximal, separable and dense computability structures. We prove that in a computable metric space which has the effective covering property and compact closed balls for a given computable sequence which is a metric basis there exists a unique maximal computability structure which contains that sequence. Furthermore, we prove that each maximal computability structure on a convex subspace of Euclidean space is dense. We also examine subspaces of Euclidean space on which each dense maximal computability structure is separable and prove that spheres, boundaries of simplices and conics are such spaces.     

On Nondeterminism,Enumeration Reducibility and Polynomial Bounds

Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e-reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non-deterministic polynomial time reducibility. We define the polynomial time e-degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe-degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy.     

Approaches to Effective Semi-Continuity of Real Functions

For semi-continuous real functions we study different computability concepts defined via computability of epigraphs and hypographs. We call a real function f lower semi-computable of type one, if its open hypograph hypo(f) is recursively enumerably open in dom(f) × ?; we call f lower semi-computable of type two, if its closed epigraph Epi(f) is recursively enumerably closed in dom(f) × ?; we call f lower semi-computable of type three, if Epi(f) is recursively closed in dom(f) × ?. We show that type one and type two semi-computability are independent and that type three semi-computability plus effectively uniform continuity implies computability, which is false for type one and type two instead of type three. We show also that the integral of a type three semi-computable real function on a computable interval is not necessarily computable.     

On resolvable primal spaces

A topological space is called resolvable if it is a union of two disjoint dense subsets, and is n-resolvable if it is a union of n mutually disjoint dense subsets. Clearly a resolvable space has no isolated points. If f is a selfmap on X, the sets A?X with f (A)?A are the closed sets of an Alexandroff topology called the primal topology 𝒫(f ) associated with f. We investigate resolvability for primal spaces (X, 𝒫(f)). Our main result is that an Alexandroff space is resolvable if and only if it has no isolated points. Moreover, n-resolvability and other related concepts are investigated for primal spaces.     

Effective Borel degrees of some topological functions

The focus of this paper is the incomputability of some topological functions (with respect to certain representations) using the tools of Borel computability theory, as introduced by V. Brattka in [3] and [4]. First, we analyze some basic topological functions on closed subsets of ?ⁿ , like closure, border, intersection, and derivative, and we prove for such functions results of Σ⁰₂‐completeness and Σ⁰₃‐completeness in the effective Borel hierarchy. Then, following [13], we re‐consider two well‐known topological results: the lemmas of Urysohn and Urysohn‐Tietze for generic metric spaces (for the latter we refer to the proof given by Dieudonné). Both lemmas define Σ⁰₂‐computable functions which in some cases are even Σ⁰₂‐complete. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Effective continuities on effective topological spaces

We extend a notion of effective continuity due to Mori, Tsujii and Yasugi to real-valued functions on effective topological spaces. Under reasonable assumptions, Type-2 computability of these functions is characterized as sequential computability and the effective continuity. We investigate effective uniform topological spaces with a separating set, and adapt the above result under some assumptions. It is also proved that effective local uniform continuity implies effective continuity under the same assumptions.     

Convex decompositions in the plane and continuous pair colorings of the irrationals

We address the structure of nonconvex closed subsets of the Euclidean plane. A closed subsetS⊆ℝ² which is not presentable as a countable union of convex sets satisfies the following dichotomy:

Antidesigns and regularity of partial spreads in dual polar graphs

We give several examples of designs and antidesigns in classical finite polar spaces. These types of subsets of maximal totally isotropic subspaces generalize the dualization of the concepts of m ‐ovoids and tight sets of points in generalized quadrangles. We also consider regularity of partial spreads and spreads. The techniques that we apply were developed by Delsarte. In some polar spaces of small rank, some of these subsets turn out to be completely regular codes. © 2010 Wiley Periodicals, Inc. J Combin Designs 19: 202‐216, 2011     

Fixed‐parameter decidability: Extending parameterized complexity analysis

We extend the reach of fixed‐parameter analysis by introducing classes of parameterized sets defined based on decidability instead of complexity. Known results in computability theory can be expressed in the language of fixed‐parameter analysis, making use of the landscape of these new classes. On the one hand this unifies results that would not otherwise show their kinship, while on the other it allows for further exchange of insights between complexity theory and computability theory. In the landscape of our fixed‐parameter decidability classes, we recover part of the classification of real numbers according to their computability. From this, using the structural properties of the landscape, we get a new proof of the existence of P ‐selective bi‐immune sets. Furthermore, we show that parameter values in parameterized sets in our uniformly fixed‐parameter decidability classes interact with both instance complexity and Kolmogorov complexity. By deriving a parameter based upper bound on instance complexity, we demonstrate how parameters convey a sense of randomness. Motivated by the instance complexity conjecture, we show that the upper bound on the instance complexity is infinitely often also an upper bound on the Kolmogorov complexity.     

Martin–Löf random generalized Poisson processes

Martin–Löf randomness was originally defined and studied in the context of the Cantor space $2^{\omega }$. In [2] probability theoretic random closed sets (RACS) are used as the foundation for the study of Martin–Löf randomness in spaces of closed sets. We use that framework to explore Martin–Löf randomness for the space of closed subsets of $\mathbb{R}$ and a particular family of measures on this space, the generalized Poisson processes. This gives a novel class of Martin–Löf random closed subsets of $\mathbb{R}$. We describe some of the properties of these Martin–Löf random closed sets; one result establishes that a real number is Martin–Löf random if and only if it is contained in some Martin–Löf random closed set.     

Convergence of Bregman Projection Methods for Solving Consistent Convex Feasibility Problems in Reflexive Banach Spaces

The problem that we consider is whether or under what conditions sequences generated in reflexive Banach spaces by cyclic Bregman projections on finitely many closed convex subsets Q _i with nonempty intersection converge to common points of the given sets.     

Null sets and games in Banach spaces

The notion of Aronszajn-null sets generalizes the notion of Lebesgue measure zero in the Euclidean space to infinite dimensional Banach spaces. We present a game-theoretic approach to Aronszajn-null sets, establish its basic properties, and discuss some ensuing open problems.     

Null sets and games in Banach spaces

The notion of Aronszajn-null sets generalizes the notion of Lebesgue measure zero in the Euclidean space to infinite dimensional Banach spaces. We present a game-theoretic approach to Aronszajn-null sets, establish its basic properties, and discuss some ensuing open problems.