Zobrazeno 1 - 10
of 48
pro vyhledávání: '"Beros, Achilles"'
A function is strongly non-recursive (SNR) if it is eventually different from each recursive function. We obtain hierarchy results for the mass problems associated with computing such functions with varying growth bounds. In particular, there is no l
Externí odkaz:
http://arxiv.org/abs/2002.01017
We show that the digraph of a nondeterministic finite automaton witnessing the automatic complexity of a word can always be taken to be planar. In the case of total transition functions studied by Shallit and Wang, planarity can fail. Let $s_q(n)$ be
Externí odkaz:
http://arxiv.org/abs/1902.00812
Whereas the usual notions of immunity -- e.g., immunity, hyperimmunity, etc. -- are associated with Cohen genericity, canonical immunity, as introduced by Beros, Khan and Kjos-Hanssen, is associated instead with Mathias genericity. Specifically, ever
Externí odkaz:
http://arxiv.org/abs/1707.03947
We study the relationship between randomness and effective bi-immunity. Greenberg and Miller have shown that for any oracle X, there are arbitrarily slow-growing DNR functions relative to X that compute no ML random set. We show that the same holds w
Externí odkaz:
http://arxiv.org/abs/1610.08615
This paper classifies the complexity of various teaching models by their position in the arithmetical hierarchy. In particular, we determine the arithmetical complexity of the index sets of the following classes: (1) the class of uniformly r.e. famil
Externí odkaz:
http://arxiv.org/abs/1610.08590
We examine sets of codes such that certain properties are invariant under the choice of oracle from a range of possible oracles and establish a connection between such codes and Medvedev reductions. In examing the complexity of such sets of \emph{uni
Externí odkaz:
http://arxiv.org/abs/1610.01650
Publikováno v:
Notre Dame J. Formal Logic 60, no. 1 (2019), 13-26
We exhibit a family of computably enumerable sets which can be learned within polynomial resource bounds given access only to a teacher, but which requires exponential resources to be learned given access only to a membership oracle. In general, we c
Externí odkaz:
http://arxiv.org/abs/1504.03623
Autor:
Beros, Achilles, de la Higuera, Colin
We prove the existence of a canonical form for semi-deterministic transducers with incomparable sets of output strings. Based on this, we develop an algorithm which learns semi-deterministic transducers given access to translation queries. We also pr
Externí odkaz:
http://arxiv.org/abs/1405.2476
Publikováno v:
Notre Dame J. Formal Logic 58, no. 2 (2017), 215-220
Given any oracle, A, we construct a basic sequence Q, computable in the jump of A, such that no A-computable real is Q-distribution-normal. A corollary to this is that there is a Delta^0_{n+1} basic sequence with respect to which no Delta^0_n real is
Externí odkaz:
http://arxiv.org/abs/1404.2178
Autor:
Beros, Achilles A.
In Diagonally Non-Computable Functions and Bi-Immunity, Carl Jockusch and Andrew Lewis proved that every DNC function computes a bi-immune set. They asked whether every DNC function computes an effectively bi-immune set. We construct a DNC function t
Externí odkaz:
http://arxiv.org/abs/1308.1324