TY - JOUR
T1 - Learning efficiency of very simple grammars from positive data
AU - Yoshinaka, Ryo
N1 - Funding Information:
This work was supported by Grant-in-Aid for Young Scientists (B-20700124) and a grant from the Global COE Program, ‘‘Center for Next-Generation Information Technology based on Knowledge Discovery and Knowledge Federation’’, from the Ministry of Education, Culture, Sports, Science and Technology of Japan.
PY - 2009/4/28
Y1 - 2009/4/28
N2 - The class of very simple grammars is known to be polynomial-time identifiable in the limit from positive data. This paper gives an even more general discussion on the efficiency of identification of very simple grammars from positive data, which includes both positive and negative results. In particular, we present an alternative efficient inconsistent learning algorithm for very simple grammars.
AB - The class of very simple grammars is known to be polynomial-time identifiable in the limit from positive data. This paper gives an even more general discussion on the efficiency of identification of very simple grammars from positive data, which includes both positive and negative results. In particular, we present an alternative efficient inconsistent learning algorithm for very simple grammars.
KW - Grammatical inference
KW - Identification in the limit
KW - Learning efficiency
KW - Very simple grammars
UR - http://www.scopus.com/inward/record.url?scp=62749186024&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=62749186024&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2009.01.012
DO - 10.1016/j.tcs.2009.01.012
M3 - Article
AN - SCOPUS:62749186024
SN - 0304-3975
VL - 410
SP - 1807
EP - 1825
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 19
ER -