The Synthesis of Language Learners

Ganesh R. Baliga, John Case, Sanjay Jain

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


An index for an r.e. class of languages (by definition) is a procedure which generates a sequence of grammars defining the class. An index for an indexed family of languages (by definition) is a procedure which generates a sequence of decision procedures defining the family. Studied is the metaproblem of synthesizing from indices for r.e. classes and for indexed families of languages various kinds of language learners for the corresponding classes or families indexed. Many positive results, as well as some negative results, are presented regarding the existence of such synthesizers. The negative results essentially provide lower bounds for the positive results. The proofs of some of the positive results yield, as pleasant corollaries, subset-principle or tell-tale style characterizations for the learnability of the corresponding classes or families indexed. For example, the indexed families of recursive languages that can be behaviorally correctly identified from positive data are surprisingly characterized by Angluin's condition 2 (the subset principle for circumventing over-generalization).

Original languageEnglish (US)
Pages (from-to)16-43
Number of pages28
JournalInformation and Computation
Issue number1
StatePublished - Jun 10 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'The Synthesis of Language Learners'. Together they form a unique fingerprint.

Cite this