TY - JOUR
T1 - Learning approximately regular languages with reversible languages
AU - Kobayashi, Satoshi
AU - Yokomori, Takashi
N1 - Funding Information:
We are grateful to the anonymous referees for valuable comments to improve the quality of this note. This work was supported in part by Grants-in-Aid for Scientific ResearchN o. 07780310( for the first author) and No. 07249201( for the second author) from the Ministry of Education, Science and Culture, Japan.
PY - 1997/3/15
Y1 - 1997/3/15
N2 - In this note, we consider the problem of learning approximately regular languages in the limit from positive data using the class of k-reversible languages. The class of k-reversible languages was introduced by Angluin (1982), and proved to be efficiently identifiable in the limit from positive data only. We show that Angluin's learning algorithm for the class of k-reversible languages can be readily adopted for the approximate identification of regular languages from positive data. Considering the negative result on the exact identifiability by Gold (1967), this approximation approach would be one of the best we could hope for learning the class of regular languages from positive data only.
AB - In this note, we consider the problem of learning approximately regular languages in the limit from positive data using the class of k-reversible languages. The class of k-reversible languages was introduced by Angluin (1982), and proved to be efficiently identifiable in the limit from positive data only. We show that Angluin's learning algorithm for the class of k-reversible languages can be readily adopted for the approximate identification of regular languages from positive data. Considering the negative result on the exact identifiability by Gold (1967), this approximation approach would be one of the best we could hope for learning the class of regular languages from positive data only.
KW - Approximate learning
KW - Computational learning theory
KW - Formal language theory
KW - Identification in the limit
UR - http://www.scopus.com/inward/record.url?scp=0031097569&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0031097569&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(96)00224-1
DO - 10.1016/S0304-3975(96)00224-1
M3 - Article
AN - SCOPUS:0031097569
SN - 0304-3975
VL - 174
SP - 251
EP - 257
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-2
ER -