Paper Info
Title
Learning approximately regular languages with reversible languages
Abstract
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.
Year
DOI
Venue
1997
10.1016/S0304-3975(96)00224-1
Theor. Comput. Sci.
Keywords
DocType
Volume
Formal language theory,Computational learning theory,reversible language,Identification in the limit,Approximate learning,regular language
Journal
174
Issue
ISSN
Citations 
1-2
Theoretical Computer Science
19
PageRank 
References 
Authors
0.85
3
2
Name
Order
Citations
PageRank
Satoshi Kobayashi113715.51
Takashi Yokomori277793.85