期刊
THEORETICAL COMPUTER SCIENCE
卷 411, 期 29-30, 页码 2741-2756出版社
ELSEVIER
DOI: 10.1016/j.tcs.2010.04.009
关键词
Grammatical inference; Mildly sontext-sensitive languages; Simple external contextual grammars; Iterative learning
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. (C) 2010 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据