Zobrazeno 1 - 10
of 99
pro vyhledávání: '"Keng Meng Ng"'
Publikováno v:
Logical Methods in Computer Science, Vol Volume 17, Issue 3 (2021)
We introduce a framework for online structure theory. Our approach generalises notions arising independently in several areas of computability theory and complexity theory. We suggest a unifying approach using operators where we allow the input to be
Externí odkaz:
https://doaj.org/article/9d1d7a616e754b6a94ffbaa010f7e937
Publikováno v:
The Journal of Symbolic Logic. :1-25
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0229f616d00c22b9515100baa516f7e0
https://doi.org/10.1017/jsl.2023.26
https://doi.org/10.1017/jsl.2023.26
Publikováno v:
Computability. 11:269-297
In her 1990 thesis, Ahmad showed that there is a so-called “Ahmad pair”, i.e., there are incomparable Σ 2 0 -enumeration degrees a 0 and a 1 such that every enumeration degree x < a 0 is ⩽ a 1 . At the same time, she also showed that there is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e196d78fdf796700c0be526c51737fd7
https://doi.org/10.3233/com-210380
https://doi.org/10.3233/com-210380
Publikováno v:
Computability. 11:187-221
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 th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::89f454b1e7c9382852bd6e4af3316f8d
https://doi.org/10.3233/com-210375
https://doi.org/10.3233/com-210375
Autor:
Michael McInerney, Keng Meng Ng
Publikováno v:
Israel Journal of Mathematics. 250:1-51
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8d8d53c9912488774457573c8273c145
https://doi.org/10.1007/s11856-022-2331-5
https://doi.org/10.1007/s11856-022-2331-5
Publikováno v:
Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore ISBN: 9789811278624
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a23a90588cc0ebf353c389d40bf7e13a
https://doi.org/10.1142/13479
https://doi.org/10.1142/13479
Publikováno v:
Journal of Logic and Computation. 31:1660-1689
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 (1931, 1934) and Kleene (1936, Math. Ann., 112, 727–742). We show that this cla
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f2ea457da1ba520929424307f12c8dbe
https://doi.org/10.1093/logcom/exab042
https://doi.org/10.1093/logcom/exab042
Autor:
Barbara F. Csima, Keng Meng Ng
Publikováno v:
Journal of Mathematical Logic. 22
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
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7f7e7f4f37b28b42c34e8c2fa610264e
https://doi.org/10.1142/s0219061322500222
https://doi.org/10.1142/s0219061322500222
Publikováno v:
Lobachevskii Journal of Mathematics. 42:693-700
An $$\alpha$$ -coloring $$\xi$$ of a structure $$\mathcal{S}$$ is distinguishing if there are no nontrivial automorphisms of $$\mathcal{S}$$ respecting $$\xi$$ . In this note we prove several results illustrating that computing the distinguishing num
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1ead95310fc77ec1756408da002cc1a7
https://doi.org/10.1134/s1995080221040053
https://doi.org/10.1134/s1995080221040053
Publikováno v:
Theoretical Computer Science. 844:195-216
We systematically investigate into the online content of finitely generated structures. The online content of a potentially infinite algebraic or combinatorial structure is perhaps best reflected by its PR-degrees (to be defined). We confirm a natura
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::bbc4f30c8cb0981ae9d33b9646309aa0
https://doi.org/10.1016/j.tcs.2020.08.021
https://doi.org/10.1016/j.tcs.2020.08.021