Learning languages from positive data and negative counterexamples

Abstract

A paradigm for learning in the limit of potentially infinite languages from all positive data and negative data counterexamples, provided in response to the conjectures made by the learner, is proposed. The computational models where, a learner gets the least negative counterexamples, the size of a negative counterexample must be bounded by the size of the positive data, and counterexample may be delayed, are considered for the paradigm. Learning power, limitation of these models, as well as their relationships with classical paradigms for learning languages in the limit are also discussed. The results show that sometimes positive data and negative counterexamples provided by teacher are not enough to compensate for full positive and negative data.