BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Achilles Beros appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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 prove that there is no learning algorithm for semi-deterministic transducers that uses only domain knowledge.
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 permitted to vacillate between a finite number of hypotheses and to make a finite number of errors. TxtFext^*_*-learning requires that hypotheses output infinitely often must describe the same finite variant of the correct set, while TxtFex^*_*-learning permits the learner to vacillate between finitely many different finite variants of the correct set. In this paper we show that TxtFex^*_* \neq TxtFext^*_*, thereby answering the question posed by Osherson, \textit{et al}. We prove this in a strong way by exhibiting a family in TxtFex^*_2 \setminus {TxtFext}^*_*.
We consider the arithmetic complexity of index sets of uniformly computably enumerable families learnable under different learning criteria. We determine the exact complexity of these sets for the standard notions of finite learning, learning in the limit, behaviorally correct learning and anomalous learning in the limit. In proving the $Σ_5^0$-completeness result for behaviorally correct learning we prove a result of independent interest; if a uniformly computably enumerable family is not learnable, then for any computable learner there is a $Δ_2^0$ enumeration witnessing failure.