6 citations · 12 across the 7 of their papers we have counts for
12 papers
From eventually different functions to pandemic numberings
Achilles A. Beros, Mushfeq Khan, Bjørn Kjos-Hanssen +1
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 s…
Planar digraphs for automatic complexity
Achilles A. Beros, Bjørn Kjos-Hanssen, Daylan Kaui Yogi
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 func…
Canonical immunity and genericity
Achilles A. Beros, Konstantinos A. Beros
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-Hans…
Classifying the Arithmetical Complexity of Teaching Models
Achilles A. Beros, Ziyuan Gao, Sandra Zilles
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 inde…
Index Sets of Universal Codes
Achilles A. Beros, Konstantinos A. Beros
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 Me…
Effective bi-immunity and randomness
Achilles A. Beros, Mushfeq Khan, Bjørn Kjos-Hanssen
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 rela…
Teachers, Learners and Oracles
Achilles A. Beros, Colin de la Higuera
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…
A Canonical Semi-Deterministic Transducer
Achilles Beros, Colin de la Higuera
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-det…
Normal numbers and limit computable Cantor series
Achilles A. Beros, Konstantinos A. Beros
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 D…
A DNC function that computes no effectively bi-immune set
Achilles A. Beros
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 functio…
Learning Theory in the Arithmetic Hierarchy
Achilles Beros
We consider the arithmetic complexity of index sets of uniformly computably enumerable families learnable under different learning criteria. We determine the exact complexity of th…
Anomalous Vacillatory Learning
Achilles Beros
In 1986, Osherson, Stob and Weinstein asked whether two variants of anomalous vacillatory learning, TxtFex^*_* and TxtFext^*_*, could be distinguished. In both, a machine is permit…