yes" for an input EFS Γ in rEFS if L(Γ) is a superset of L*), and outputs a string in L*)-L(Γ), otherwise. An oracle for membership queries answers "yes" for an input string w if w is included in L*), and answers "no", otherwise. We show that any EFS in rEFS is exactly identifiable in polynomial time using membership and superset queries. Moreover, for other types of queries, we show that there exists no polynomial time learning algorithm for rEFS by using the queries. This result indicates the hardness of learning the class rEFS in the exact learning model, in general." />


Learning of Elementary Formal Systems with Two Clauses Using Queries

Hirotaka KATO  Satoshi MATSUMOTO  Tetsuhiro MIYAHARA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.2   pp.172-180
Publication Date: 2009/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.172
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
computational learning theory,  query learning,  learning of logic programs,  

Full Text: PDF(257KB)>>
Buy this Article




Summary: 
An elementary formal system, EFS for short, is a kind of logic program over strings, and regarded as a set of rules to generate a language. For an EFS Γ, the language L(Γ) denotes the set of all strings generated by Γ. We consider a new form of EFS, called a restricted two-clause EFS, and denote by rEFS the set of all restricted two-clause EFSs. Then we study the learnability of rEFS in the exact learning model. The class rEFS contains the class of regular patterns, which is extensively studied in Learning Theory. Let Γ* be a target EFS in rEFS of learning. In the exact learning model, an oracle for superset queries answers "yes" for an input EFS Γ in rEFS if L(Γ) is a superset of L*), and outputs a string in L*)-L(Γ), otherwise. An oracle for membership queries answers "yes" for an input string w if w is included in L*), and answers "no", otherwise. We show that any EFS in rEFS is exactly identifiable in polynomial time using membership and superset queries. Moreover, for other types of queries, we show that there exists no polynomial time learning algorithm for rEFS by using the queries. This result indicates the hardness of learning the class rEFS in the exact learning model, in general.