Zobrazeno 1 - 10
of 97
pro vyhledávání: '"Klaus Ambos-Spies"'
Publikováno v:
The Journal of Symbolic Logic. 86:1282-1292
We solve a longstanding question of Soare by showing that if ${\mathbf d}$ is a non-low $_2$ computably enumerable degree then ${\mathbf d}$ contains a c.e. set with no r-maximal c.e. superset.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::236c26da4a43fdf514e619570c637950
https://doi.org/10.1017/jsl.2021.72
https://doi.org/10.1017/jsl.2021.72
Autor:
Klaus Ambos-Spies, Timur Bakibayev
Publikováno v:
Theory of Computing Systems. 63:1388-1412
Lutz (SIAM J. Comput. 24(6), 1170–1189, 1995) proposed the following generalization of hardness: While a problem A is hard for a complexity class C if all problems in C can be reduced to A, Lutz calls a problem weakly hard if a nonnegligible part o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::cbdee4317e3ab30c2dbe1ef517da2772
https://doi.org/10.1007/s00224-019-09920-4
https://doi.org/10.1007/s00224-019-09920-4
Autor:
Klaus Ambos-Spies
Publikováno v:
Logic, Computation and Rigorous Methods ISBN: 9783030760199
Logic, Computation and Rigorous Methods
Logic, Computation and Rigorous Methods
A computably enumerable (c.e.) set A is mitotic if it can be split into two c.e. sets \(A_0\) and \(A_1\) which are Turing equivalent to A. Glaser et al. [3] introduced two variants of this notion. The first variant weakens mitoticity by not requirin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d4b838e9e2e94db42a678874c0d94fff
https://doi.org/10.1007/978-3-030-76020-5_2
https://doi.org/10.1007/978-3-030-76020-5_2
Autor:
Klaus Ambos-Spies
Publikováno v:
Computability. 7:237-258
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5723b13e4c07a47c7088b5c52e5bb38d
https://doi.org/10.3233/com-180088
https://doi.org/10.3233/com-180088
Autor:
Elvira Mayordomo, Klaus Ambos-Spies
Publikováno v:
complexity, logic, and recursion theory
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::da87460f84aaddd637194818acf5f9c1
https://doi.org/10.1201/9780429187490-1
https://doi.org/10.1201/9780429187490-1
Autor:
Xizhong Zheng, Klaus Ambos-Spies
Publikováno v:
Computing with Foresight and Industry ISBN: 9783030229955
CiE
CiE
A real number is called left c.e. (right c.e.) if it is the limit of an increasing (decreasing) computable sequence of rational numbers. In particular, if a left c.e. real has a c.e. binary expansion, then it is called strongly c.e. While the strongl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::461b438a338c0eee501d8b17d08a3bd5
https://doi.org/10.1007/978-3-030-22996-2_27
https://doi.org/10.1007/978-3-030-22996-2_27
Autor:
Klaus Ambos-Spies
Publikováno v:
Sailing Routes in the World of Computation ISBN: 9783319944173
CiE
CiE
Downey et al. [5] have introduced the array noncomputable (a.n.c.) computably enumerable (c.e.) sets which capture certain multiple permitting arguments. In this way they have classified the c.e. degrees below which certain constructions can be perfo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::419eb3c9e47a38a5403269a1ebba72d6
https://doi.org/10.1007/978-3-319-94418-0_3
https://doi.org/10.1007/978-3-319-94418-0_3
Autor:
Klaus Ambos-Spies, Timur Bakibayev
Publikováno v:
Theoretical Computer Science. 494:2-12
A set A is nontrivial for the linear exponential time class E=DTIME(2^l^i^n) if [email protected]?E and the sets from E which can be reduced to A are not from a single level DTIME(2^k^n) of the linear exponential hierarchy. Similarly, a set A is nont
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4570c337465857053bd023af27853b1c
https://doi.org/10.1016/j.tcs.2012.05.022
https://doi.org/10.1016/j.tcs.2012.05.022
Publikováno v:
Annals of Pure and Applied Logic. 164:577-588
We show that, in the partial ordering ( R cl , ⩽ ) of the computably enumerable (c.e.) computable Lipschitz (cl) degrees, there is a degree a > 0 such that the class of the degrees which do not cup to a is not bounded by any degree less than a. Sin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b398f924b37cda89dc1219639e9b562a
https://doi.org/10.1016/j.apal.2012.11.002
https://doi.org/10.1016/j.apal.2012.11.002