Learning of Elementary Formal Systems with Two Clauses Using Queries

概要

論文の詳細を見る
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 $r{\\cal EF\\!S}$ the set of all restricted two-clause EFSs. Then we study the learnability of $r{\\cal EF\\!S}$ in the exact learning model. The class $r{\\cal EF\\!S}$ contains the class of regular patterns, which is extensively studied in Learning Theory. Let Γ* be a target EFS in $r{\\cal EF\\!S}$ of learning. In the exact learning model, an oracle for superset queries answers “yes” for an input EFS Γ in $r{\\cal EF\\!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 $r{\\cal EF\\!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 $r{\\cal EF\\!S}$ by using the queries. This result indicates the hardness of learning the class $r{\\cal EF\\!S}$ in the exact learning model, in general.
（社）電子情報通信学会の論文
2009-02-01