Paper Info
Title
Learning of Elementary Formal Systems with Two Clauses Using Queries
Abstract
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 Γ. Many researchers studied the learnability of EFSs in various learning models. In this paper, we introduce a subclass of EFSs, denoted by rEFSr\cal E\!F\!S, and study the learnability of rEFSr\cal E\!F\!S in the exact learning model. The class rEFSr\cal E\!F\!S contains the class of regular patterns, which is extensively studied in Learning Theory. Let Γ ∗  be a target EFS of learning in rEFSr\cal E\!F\!S. In the exact learning model, an oracle for superset queries answers “yes” for an input EFS Γ in rEFSr\cal E\!F\!S 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 rEFSr\cal E\!F\!S 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 rEFSr\cal E\!F\!S by using the queries. This result indicates the hardness of learning the class rEFSr\cal E\!F\!S in the exact learning model, in general.
Year
DOI
Venue
2009
10.1007/11564089_18
IEICE Transactions
Keywords
Field
DocType
polynomial time,computational learning theory,learning theory
Discrete mathematics,Formal system,Logic program,Subset and superset,Existential quantification,Oracle,Artificial intelligence,Time complexity,Learnability,String (computer science),Machine learning,Mathematics
Journal
Volume
Issue
ISSN
92-D
2
0302-9743
ISBN
Citations 
PageRank 
3-540-29242-X
0
0.34
References 
Authors
7
3
Name
Order
Citations
PageRank
Hirotaka Kato101.01
Satoshi Matsumoto2558.66
Tetsuhiro Miyahara326732.75