Synthesizing enumeration techniques for language learning
Ganesh R. Baliga, John Case, Sanjay K. Jain · 1996
This paper provides positive and negative results on algorithmically synthesizing, from grammars and from decision procedures for classes of languages, learning machines for identifying, from positive data, grammars for the languages in those classes. In the process, the uniformly decidable classes of recursive languages that can be behaviorally correctly identified from positive data are surprisingly characterized by Angluin's 1980 Condition 2 (the subset principle for preventing overgeneralization) . 1 Introduction In the context of learning programs in the limit for functions [KW80, AS83, OSW86b], a variety of enumeration techniques [Gol67, BB75, Wie90, Ful90b] are important and ubiquitous. Here is the archetypal case. Suppose one has an r.e. set P of programs for computing total functions. One proceeds as follows. At each point that one is given data about an input function, one conjectures the first program, if any, listed in P that is correct on the data seen through that point....