A NOTE ON INADEQUACY OF THE MODEL FOR LEARNING FROM QUERIES

''Learning correctly from queries'' is a formal learning model propose d by Angluin. In this model, for a class GAMMA of language representat ions, a learner asks queries to a teacher of an unknown language L(q) which can be represented by some G(q) is-an-element-of GAMMA, and even tually outputs a language representation G is-an-element-of GAMMA whic h represents L(q) and halts. An algorithm (leaner) A is said to learn a class LAMBDA of languages represented by GAMMA in the weak definitio n if the time complexity of A is some polynomial of n and m, where n i s the minimum size of the language representations in GAMMA which repr esent L(q), and m is the maximum length of the counterexamples returne d in an execution. On the other hand, A is said to learn LAMBDA repres ented by GAMMA in the strong definition if at any point tau of the exe cution, the time consumed up to tau is some polynomial of n and m, whe re n is the same as above, and m is the maximum length of the countere xamples returned up to tau. In this paper, adequacy of the model is ex amined, and it is shown that both in the weak and strong definitions, there exist learners which extract a long counterexample, and identify L(q) by using equivalence queries exhaustively. For example, there ex ists a learner which learns the class CFL of context-free languages re presented by the class CFG of context-free grammars in the weak defini tion using only equivalence queries. Next, two restrictions concerning with learnability criteria are introduced. Proper termination conditi on is that when a teacher replies with ''yes'' to an equivalence query , then the learner must halt immediately. The other condition, called LBC-condition, is that in the weak/strong definition, the time complex ity must be some polynomial of n and log m. In this paper, it is shown that under these conditions, there still exist learners which execute exhaustive search. For instance, there exists a learner which learns CFL represented by CFG in the weak definition using membership queries and equivalence queries under the proper termination condition, and t here also exists a learner that learns CFL represented by CFG in the s trong definition using subset queries and superset queries under LBC-c ondition. These results suggest that the weak definition is not an ade quate learning model even if the proper termination condition is assum ed. Also, the model becomes inadequate in the strong definition if som e combination of queries, such as subset queries and superset queries, is used instead of equivalence queries. Many classes of languages bec ome learnable by our ''extracting long counterexample'' technique. How ever, it is still open whether or not CFL represented by CFG is learna ble in the strong definition from membership queries and equivalence q ueries, although the answer is known to be negative if at least one of (1) quadratic residues modulo a composite, (2) inverting RSA encrypti on, or (3) factoring Blum integers, is intractable.