Please use this identifier to cite or link to this item:
|Title:||Iterative learning of simple external contextual languages|
Mildly sontext-sensitive languages
Simple external contextual grammars
|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. 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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Jan 11, 2019
WEB OF SCIENCETM
checked on Jan 2, 2019
checked on Dec 8, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.