Learning Elementary Formal Systems with Queries
Hiroshi Sakamoto, Kouichi Hirata, Hiroki Arimura · Institutional Repositories DataBase (IRDB) · 2000
An elementary formal system (EFS , for short) is a kind of logic program which directly manipulates character strings. A number of researches have investigated the ability of EFS as an uniform framework for language learning in various learning models including model inference, inductive inference, and PAC-learning. In this paper, we investigate the polynomial time learnability of EFS from the view of active learning allowing membership queries. Positive results include the polynomial time learnability of the class of terminating HEFS of variable-occurrence k and arity r from equivalence queries and entailment membership queries with the information on termination. We also presented a lower bound result showing that the algorithm is near optimal in the query complexity. Negative results include a series of representation-independent hardness results, which fill the gap between the learnable and the non-learnable subclasses of EFS in our knowledge. Particularly, we showed th...