Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2010.04.009
Title: Iterative learning of simple external contextual languages
Authors: Becerra-Bonache, L.
Case, J.
Jain, S. 
Stephan, F. 
Keywords: Grammatical inference
Iterative learning
Mildly sontext-sensitive languages
Simple external contextual grammars
Issue Date: 2010
Source: Becerra-Bonache, L., Case, J., Jain, S., Stephan, F. (2010). Iterative learning of simple external contextual languages. Theoretical Computer Science 411 (29-30) : 2741-2756. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2010.04.009
Abstract: It is investigated for which choice of a parameter q, denoting the number of contexts, the class of simple external contextual languages is iteratively learnable. On the one hand, the class admits, for all values of q, polynomial time learnability provided an adequate choice of the hypothesis space is given. On the other hand, additional constraints like consistency and conservativeness or the use of a one-one hypothesis space changes the picture - iterative learning limits the long term memory of the learner to the current hypothesis and these constraints further hinder storage of information via padding of this hypothesis. It is shown that if q > 3, then simple external contextual languages are not iteratively learnable using a class preserving one-one hypothesis space, while for q = 1 it is iteratively learnable, even in polynomial time. It is also investigated for which choice of the parameters the simple external contextual languages can be learnt by a consistent and conservative iterative learner. © 2010 Elsevier B.V.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/43094
ISSN: 03043975
DOI: 10.1016/j.tcs.2010.04.009
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

9
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

8
checked on Nov 19, 2017

Page view(s)

58
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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