30 found
Order:
  1.  36
    Universal computably enumerable equivalence relations.Uri Andrews, Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Luca San Mauro & Andrea Sorbi - 2014 - Journal of Symbolic Logic 79 (1):60-88.
  2.  24
    Automatic and polynomial-time algebraic structures.Nikolay Bazhenov, Matthew Harrison-Trainor, Iskander Kalimullin, Alexander Melnikov & Keng Meng Ng - 2019 - Journal of Symbolic Logic 84 (4):1630-1669.
    A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is ${\rm{\Sigma (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  3.  25
    On the Degree Structure of Equivalence Relations Under Computable Reducibility.Keng Meng Ng & Hongyuan Yu - 2019 - Notre Dame Journal of Formal Logic 60 (4):733-761.
    We study the degree structure of the ω-c.e., n-c.e., and Π10 equivalence relations under the computable many-one reducibility. In particular, we investigate for each of these classes of degrees the most basic questions about the structure of the partial order. We prove the existence of the greatest element for the ω-c.e. and n-computably enumerable equivalence relations. We provide computable enumerations of the degrees of ω-c.e., n-c.e., and Π10 equivalence relations. We prove that for all the degree classes considered, upward density (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  4.  42
    The importance of Π1 0 classes in effective randomness.George Barmpalias, Andrew E. M. Lewis & Keng Meng Ng - 2010 - Journal of Symbolic Logic 75 (1):387-400.
    We prove a number of results in effective randomness, using methods in which Π⁰₁ classes play an essential role. The results proved include the fact that every PA Turing degree is the join of two random Turing degrees, and the existence of a minimal pair of LR degrees below the LR degree of the halting problem.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  5.  29
    Turing degrees in Polish spaces and decomposability of Borel functions.Vassilios Gregoriades, Takayuki Kihara & Keng Meng Ng - 2020 - Journal of Mathematical Logic 21 (1):2050021.
    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 separable metrizable space. Our techniques employ deep results from effective descriptive set theory and recursion theory. In fact it is essential to extend several prominent results in recursion theory (e.g. the Shore-Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results on (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  6.  24
    On Δ 2 0 -categoricity of equivalence relations.Rod Downey, Alexander G. Melnikov & Keng Meng Ng - 2015 - Annals of Pure and Applied Logic 166 (9):851-880.
  7.  33
    Complexity of equivalence relations and preorders from computability theory.Egor Ianovski, Russell Miller, Keng Meng Ng & André Nies - 2014 - Journal of Symbolic Logic 79 (3):859-881.
    We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relationsR,S, a componentwise reducibility is defined byR≤S⇔ ∃f∀x, y[x R y↔fS f].Here,fis taken from a suitable class of effective functions. For us the relations will be on natural numbers, andfmust be computable. We show that there is a${\rm{\Pi }}_1^0$-complete equivalence relation, but no${\rm{\Pi }}_k^0$-complete fork≥ 2. We show that${\rm{\Sigma }}_k^0$preorders arising naturally in the above-mentioned areas are${\rm{\Sigma }}_k^0$-complete. This includes polynomial timem-reducibility on (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  8.  28
    Abelian p-groups and the Halting problem.Rodney Downey, Alexander G. Melnikov & Keng Meng Ng - 2016 - Annals of Pure and Applied Logic 167 (11):1123-1138.
  9.  22
    Splitting into degrees with low computational strength.Rod Downey & Keng Meng Ng - 2018 - Annals of Pure and Applied Logic 169 (8):803-834.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  10.  61
    Limits on jump inversion for strong reducibilities.Barbara F. Csima, Rod Downey & Keng Meng Ng - 2011 - Journal of Symbolic Logic 76 (4):1287-1296.
    We show that Sacks' and Shoenfield's analogs of jump inversion fail for both tt- and wtt-reducibilities in a strong way. In particular we show that there is a ${\mathrm{\Delta }}_{2}^{0}$ set B > tt ∅′ such that there is no c.e. set A with A′ ≡ wtt B. We also show that there is a ${\mathrm{\Sigma }}_{2}^{0}$ set C > tt ∅′ such that there is no ${\mathrm{\Delta }}_{2}^{0}$ set D with D′ ≡ wtt C.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  11.  44
    A Friedberg enumeration of equivalence structures.Rodney G. Downey, Alexander G. Melnikov & Keng Meng Ng - 2017 - Journal of Mathematical Logic 17 (2):1750008.
    We solve a problem posed by Goncharov and Knight 639–681, 757]). More specifically, we produce an effective Friedberg enumeration of computable equivalence structures, up to isomorphism. We also prove that there exists an effective Friedberg enumeration of all isomorphism types of infinite computable equivalence structures.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  12.  19
    Incomparability in local structures of s -degrees and Q -degrees.Irakli Chitaia, Keng Meng Ng, Andrea Sorbi & Yue Yang - 2020 - Archive for Mathematical Logic 59 (7-8):777-791.
    We show that for every intermediate \ s-degree there exists an incomparable \ s-degree. As a consequence, for every intermediate \ Q-degree there exists an incomparable \ Q-degree. We also show how these results can be applied to provide proofs or new proofs of upper density results in local structures of s-degrees and Q-degrees.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  13.  16
    Effective Domination and the Bounded Jump.Keng Meng Ng & Hongyuan Yu - 2020 - Notre Dame Journal of Formal Logic 61 (2):203-225.
    We study the relationship between effective domination properties and the bounded jump. We answer two open questions about the bounded jump: We prove that the analogue of Sacks jump inversion fails for the bounded jump and the wtt-reducibility. We prove that no c.e. bounded high set can be low by showing that they all have to be Turing complete. We characterize the class of c.e. bounded high sets as being those sets computing the Halting problem via a reduction with use (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  14.  20
    On strongly jump traceable reals.Keng Meng Ng - 2008 - Annals of Pure and Applied Logic 154 (1):51-69.
    In this paper we show that there is no minimal bound for jump traceability. In particular, there is no single order function such that strong jump traceability is equivalent to jump traceability for that order. The uniformity of the proof method allows us to adapt the technique to showing that the index set of the c.e. strongly jump traceables is image-complete.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  15.  34
    On very high degrees.Keng Meng Ng - 2008 - Journal of Symbolic Logic 73 (1):309-342.
    In this paper we show that there is a pair of superhigh r.e. degree that forms a minimal pair. An analysis of the proof shows that a critical ingredient is the growth rates of certain order functions. This leads us to investigate certain high r.e. degrees, which resemble ∅′ very closely in terms of ∅′-jump traceability. In particular, we will construct an ultrahigh degree which is cappable.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  16.  34
    Effective Packing Dimension and Traceability.Rod Downey & Keng Meng Ng - 2010 - Notre Dame Journal of Formal Logic 51 (2):279-290.
    We study the Turing degrees which contain a real of effective packing dimension one. Downey and Greenberg showed that a c.e. degree has effective packing dimension one if and only if it is not c.e. traceable. In this paper, we show that this characterization fails in general. We construct a real $A\leq_T\emptyset''$ which is hyperimmune-free and not c.e. traceable such that every real $\alpha\leq_T A$ has effective packing dimension 0. We construct a real $B\leq_T\emptyset'$ which is not c.e. traceable such (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  17.  59
    Lowness for effective Hausdorff dimension.Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Daniel D. Turetsky & Rebecca Weber - 2014 - Journal of Mathematical Logic 14 (2):1450011.
    We examine the sequences A that are low for dimension, i.e. those for which the effective dimension relative to A is the same as the unrelativized effective dimension. Lowness for dimension is a weakening of lowness for randomness, a central notion in effective randomness. By considering analogues of characterizations of lowness for randomness, we show that lowness for dimension can be characterized in several ways. It is equivalent to lowishness for randomness, namely, that every Martin-Löf random sequence has effective dimension (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  18.  8
    Limit complexities, minimal descriptions, and N-randomness.Rodney Graham Downey, Lu Liu, Keng Meng Ng & Daniel Turetsky - forthcoming - Journal of Symbolic Logic:1-16.
    Let K denote prefix-free Kolmogorov complexity, and let $K^A$ denote it relative to an oracle A. We show that for any n, $K^{\emptyset ^{(n)}}$ is definable purely in terms of the unrelativized notion K. It was already known that 2-randomness is definable in terms of K (and plain complexity C) as those reals which infinitely often have maximal complexity. We can use our characterization to show that n-randomness is definable purely in terms of K. To do this we extend a (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19.  3
    Punctually presented structures II: comparing presentations.Marina Dorzhieva, Rodney Downey, Ellen Hammatt, Alexander G. Melnikov & Keng Meng Ng - forthcoming - Archive for Mathematical Logic:1-26.
    We investigate the problem of punctual (fully primitive recursive) presentability of algebraic structures up to primitive recursive and computable isomorphism. We show that for mono-unary structures and undirected graphs, if a structure is not punctually categorical then it has infinitely many punctually non-isomorphic punctual presentations. We also show that the punctual degrees of any computably almost rigid structure as well as the order ($$\mathbb {Z},<$$ Z, < ) are dense. Finally we characterise the Boolean algebras which have a punctually 1-decidable (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  20.  30
    Primitive recursive equivalence relations and their primitive recursive complexity.Luca San Mauro, Nikolay Bazhenov, Keng Meng Ng & Andrea Sorbi - forthcoming - Computability.
    The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations R and S on natural numbers, R is computably reducible to S if there is a computable function f:ω→ω that induces an injective map from R-equivalence classes to S-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, such as the polynomial-time reducibility. (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  21.  2
    Computably and punctually universal spaces.Ramil Bagaviev, Ilnur I. Batyrshin, Nikolay Bazhenov, Dmitry Bushtets, Marina Dorzhieva, Heer Tern Koh, Ruslan Kornev, Alexander G. Melnikov & Keng Meng Ng - 2025 - Annals of Pure and Applied Logic 176 (1):103491.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  22.  42
    Jump inversions inside effectively closed sets and applications to randomness.George Barmpalias, Rod Downey & Keng Meng Ng - 2011 - Journal of Symbolic Logic 76 (2):491 - 518.
    We study inversions of the jump operator on ${\mathrm{\Pi }}_{1}^{0}$ classes, combined with certain basis theorems. These jump inversions have implications for the study of the jump operator on the random degrees—for various notions of randomness. For example, we characterize the jumps of the weakly 2-random sets which are not 2-random, and the jumps of the weakly 1-random relative to 0′ sets which are not 2-random. Both of the classes coincide with the degrees above 0′ which are not 0′-dominated. A (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  23. The importance of $\Pi _1^0$ classes in effective randomness. The Journal of Symbolic Logic, vol. 75.George Barmpalias, Andrew E. M. Lewis, Keng Meng Ng & Frank Stephan - 2012 - Bulletin of Symbolic Logic 18 (3):409-412.
  24.  16
    Every Δ20 degree is a strong degree of categoricity.Barbara F. Csima & Keng Meng Ng - 2022 - Journal of Mathematical Logic 22 (3).
    A strong degree of categoricity is a Turing degree [Formula: see text] such that there is a computable structure [Formula: see text] that is [Formula: see text]-computably categorical (there is a [Formula: see text]-computable isomorphism between any two computable copies of [Formula: see text]), and such that there exist two computable copies of [Formula: see text] between which every isomorphism computes [Formula: see text]. The question of whether every [Formula: see text] degree is a strong degree of categoricity has been (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  25.  45
    Strengthening prompt simplicity.David Diamondstone & Keng Meng Ng - 2011 - Journal of Symbolic Logic 76 (3):946 - 972.
    We introduce a natural strengthening of prompt simplicity which we call strong promptness, and study its relationship with existing lowness classes. This notion provides a ≤ wtt version of superlow cuppability. We show that every strongly prompt c.e. set is superlow cuppable. Unfortunately, strong promptness is not a Turing degree notion, and so cannot characterize the sets which are superlow cuppable. However, it is a wtt-degree notion, and we show that it characterizes the degrees which satisfy a wtt-degree notion very (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  26.  27
    Categorical linearly ordered structures.Rod Downey, Alexander Melnikov & Keng Meng Ng - 2019 - Annals of Pure and Applied Logic 170 (10):1243-1255.
  27.  18
    Ω-change randomness and weak Demuth randomness.Johanna N. Y. Franklin & Keng Meng Ng - 2014 - Journal of Symbolic Logic 79 (3):776-791.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  28.  14
    Computable linear orders and products.Andrey N. Frolov, Steffen Lempp, Keng Meng Ng & Guohua Wu - 2020 - Journal of Symbolic Logic 85 (2):605-623.
    We characterize the linear order types $\tau $ with the property that given any countable linear order $\mathcal {L}$, $\tau \cdot \mathcal {L}$ is a computable linear order iff $\mathcal {L}$ is a computable linear order, as exactly the finite nonempty order types.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  29.  10
    Separating weak α-change and α-change genericity.Michael McInerney & Keng Meng Ng - 2022 - Annals of Pure and Applied Logic 173 (7):103134.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  30.  41
    On the Degrees of Diagonal Sets and the Failure of the Analogue of a Theorem of Martin.Keng Meng Ng - 2009 - Notre Dame Journal of Formal Logic 50 (4):469-493.
    Semi-hyperhypersimple c.e. sets, also known as diagonals, were introduced by Kummer. He showed that by considering an analogue of hyperhypersimplicity, one could characterize the sets which are the Halting problem relative to arbitrary computable numberings. One could also consider half of splittings of maximal or hyperhypersimple sets and get another variant of maximality and hyperhypersimplicity, which are closely related to the study of automorphisms of the c.e. sets. We investigate the Turing degrees of these classes of c.e. sets. In particular, (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark