Please use this identifier to cite or link to this item:
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
Citation: 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.
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
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.


checked on May 20, 2019


checked on May 20, 2019

Page view(s)

checked on May 25, 2019

Google ScholarTM



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