Learning of Elementary Formal Systems with Two Clauses using Queries and Their Languages(New Trends in Theory of Computation and Algorithm)
Hirotaka Kato, Satoshi Matsumoto, Tetsuhiro Miyahara · Kyoto University Research Information Repository (Kyoto University) · 2006
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 $\Gamma$ , the language $L(\Gamma)$ denotes the set of all strings generated by F. Many researchers stud- ied the learnability of EFSs in various learning models.In this paper, we introduce a subclass of EFSs, denoted by $r\epsilon \mathcal{P}S$ , and study the learn- ability of $r\epsilon \mathcal{P}S$ in the exact learning model.The class $r\epsilon\pi$ contains the class of regular patterns, which is extensively studied in Learning Theory.Let $\Gamma_{*}$ be a target EFS of learning in $r\mathcal{E}\mathcal{F}S$ .In the exact learning model, an oracle for superset queries answers "yes" for an input EFS $\Gamma$ in $r\epsilon FS$ if $L(\Gamma)$ is a superset of $L(\Gamma_{*})$ , and outputs a string in $L(\Gamma.)-L(\Gamma)$, otherwise.An oracle for membership queries answers "yes" for an input string $w$ if $w$ is included in $L(\Gamma_{*})$ , and answers " $no^{)}'$ , otherwise.We show that any EFS in $rS\mathcal{P}S$ is exactly iden- tifiable in polynomial time using membership and superset queries.Moreover, for other types of queries, we show that there exists no polyno- mial time learning algorithm for $r\mathcal{E}FS$ by using the queries.This result indicates the hardness of learning the class $r\mathcal{E}FS$ in the exact learning model, in general.