Authors: Hirotaka Kato, Satoshi Matsumoto, and Tetsuhiro Miyahara
Source: Algorithmic Learning Theory, 16th International Conference, ALT 2005, Singapore, October 2005, Proceedings, (Sanjay Jain, Hans Ulrich Simon and Etsuji Tomita, Eds.), Lecture Notes in Artificial Intelligence 3734, pp. 211 - 225, Springer 2005.
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 and study the learnability of in the exact learning model. The class contains the class of regular patterns, which is extensively studied in Learning Theory. Let Γ* be a target EFS of learning in In the exact learning model, an oracle for superset queries answers “yes” for an input EFS Γ in 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 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 by using the queries. This result indicates the hardness of learning the class in the exact learning model, in general.
©Copyright 2005, Springer