A regular pattern is a string consisting of constant symbols and distinct variable symbols. The language of a regular pattern is the set of all constant strings obtained by replacing all variable symbols in the regular pattern with non-empty strings. The present paper deals with the learning problem of languages of regular patterns within Angluin's query learning model, which is an established mathematical model of learning via queries in computational learning theory. The class of languages of regular patterns was known to be identifiable from one positive example using a polynomial number of membership queries, in the query learning model. In present paper, we show that the class of languages of regular patterns is identifiable from one positive example using a linear number of membership queries, with respect to the length of the positive example.

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.

We propose a learning method combining query learning and a "genetic translator" we previously developed. Query learning is a useful technique for high-accuracy, high-speed learning and reduction of training sample size. However, it has not been applied to practical optical character readers (OCRs) because human beings cannot recognize queries as character images in the feature space used in practical OCR devices. We previously proposed a character image reconstruction method using a genetic algorithm. This method is applied as a "translator" from feature space for query learning of character recognition. The results of an experiment with hand-written numeral recognition show the possibility of training sample size reduction.

We consider the role of equivalence queries in learning unknown concepts using membership and equivalence queries. Equivalence queries have the following two roles: (R1) indicating whether a learning algorithm has succeeded to learn the unknown concept and (R2) providing counterexamples. In this paper, we consider the learning using membership and equivalence queries but using only the (R2) part of equivalence queries. In order to gain an insight into the learning membership and equivalence queries but using only the (R2) part of equivalence queries, we define equivalence-detecting problem". Let C be a representation class which is polynomial time learnable using membership and equivalence queries. We show that if the equivalence-detecting problem for C is polynomial time solvable then C is polynomial time learnable using membership and equivalence queries without using (R1). Moreover, we show that under certain conditions, the two notions, polynomial time solvability of equivalence-detecting problem" and polynomial time learnability using membership and equivalence queries without using (R1)", are equivalent. For concrete examples, we prove that dfas are polynomial time learnable using membership and equivalence queries without using (R1) in the learning situation where the algorithm is informed the number of states of the minimum states dfa accepting the target set in advance. On the other hand, we show that the equivalence-detecting problem for dfas are not solvable in the learning situation where the algorithm can use no additional information. This result together with our main result shows that, in this learning situation, the (R1) part of equivalence queries are necessary to learn dfas using membership and equivalence queries.