Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2009.01.011
Title: Prescribed learning of r.e. classes
Authors: Jain, S. 
Stephan, F. 
Ye, N. 
Keywords: Formal languages
Inductive inference
Prescribed learning
Recursion theory
Issue Date: 2009
Source: Jain, S., Stephan, F., Ye, N. (2009). Prescribed learning of r.e. classes. Theoretical Computer Science 410 (19) : 1796-1806. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2009.01.011
Abstract: This work extends studies of Angluin, Lange and Zeugmann on the dependence of learning on the hypothesis space chosen for the language class in the case of learning uniformly recursive language classes. The concepts of class-comprising (where the learner can choose a uniformly recursively enumerable superclass as the hypothesis space) and class-preserving (where the learner has to choose a uniformly recursively enumerable hypothesis space of the same class) are formulated in their study. In subsequent investigations, uniformly recursively enumerable hypothesis spaces have been considered. In the present work, we extend the above works by considering the question of whether learners can be effectively synthesized from a given hypothesis space in the context of learning uniformly recursively enumerable language classes. In our study, we introduce the concepts of prescribed learning (where there must be a learner for every uniformly recursively enumerable hypothesis space of the same class) and uniform learning (like prescribed, but the learner has to be synthesized effectively from an index of the hypothesis space). It is shown that while for explanatory learning, these four types of learnability coincide, some or all are different for other learning criteria. For example, for conservative learning, all four types are different. Several results are obtained for vacillatory and behaviourally correct learning; three of the four types can be separated, however the relation between prescribed and uniform learning remains open. It is also shown that every (not necessarily uniformly recursively enumerable) behaviourally correct learnable class has a prudent learner, that is, a learner using a hypothesis space such that the learner learns every set in the hypothesis space. Moreover the prudent learner can be effectively built from any learner for the class. © 2009 Elsevier B.V. All rights reserved.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/43056
ISSN: 03043975
DOI: 10.1016/j.tcs.2009.01.011
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

3
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

1
checked on Nov 18, 2017

Page view(s)

46
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.