4 citations · 8 across the 8 of their papers we have counts for
10 papers
sp-Homogeneous Linear Orderings
Wesley Calvert, Douglas Cenzer, David Gonzalez +2
We study linear orderings expanded by functions for successor and predecessor. The successor and predecessor on linear orderings capture the relatively intrinsically computably enu…
The subTuring degrees
Takayuki Kihara, Keng Meng Ng
In this article, we introduce a notion of reducibility for partial functions on the natural numbers, which we call subTuring reducibility. One important aspect is that the subTurin…
Finite final segments of the d.c.e. Turing degrees
Steffen Lempp, Yiqun Liu, Yong Liu +3
We prove that every finite distributive lattice is isomorphic to a final segment of the d.c.e. Turing degrees (i.e., the degrees of differences of computably enumerable sets). As a…
Computable topological groups
Heer Tern Koh, Alexander Melnikov, Keng Meng Ng
We investigate what it means for a (Hausdorff, second-countable) topological group to be computable. We compare several potential definitions in the literature. We relate these not…
A recursion theoretic foundation of computation over real numbers
Keng Meng Ng, Nazanin R. Tavana, Yue Yang
We define a class of computable functions over real numbers using functional schemes similar to the class of primitive and partial recursive functions defined by Gödel and Kleene.…
Enumeration degrees and non-metrizable topology
Takayuki Kihara, Keng Meng Ng, Arno Pauly
The enumeration degrees of sets of natural numbers can be identified with the degrees of difficulty of enumerating neighborhood bases of points in a universal second-countable $T_0…
Turing degrees in Polish spaces and decomposability of Borel functions
Vassilios Gregoriades, Takayuki Kihara, Keng Meng Ng
We give a partial answer to an important open problem in descriptive set theory, the Decomposability Conjecture for Borel functions on an analytic subset of a Polish space to a sep…
Finitary reducibility on equivalence relations
Russell Miller, Keng Meng Ng
We introduce the notion of finitary computable reducibility on equivalence relations on the natural numbers. This is a weakening of the usual notion of computable reducibility, and…
An analogy between cardinal characteristics and highness properties of oracles
Jörg Brendle, Andrew Brooke-Taylor, Keng Meng Ng +1
We present an analogy between cardinal characteristics from set theory and highness properties from computability theory, which specify a sense in which a Turing oracle is computat…
Complexity of equivalence relations and preorders from computability theory
Egor Ianovski, Keng Meng Ng, Russell Miller +1
We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relations , a componentwise reducibility…