4 citations · 8 across the 8 of their papers we have counts for
8 papers · 1 filter
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…
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…