The Synthesis of Language Learners

Ganesh R. Baliga, John Case, Sanjay Jain

Research output: Contribution to journalArticle

29 Scopus citations

Abstract

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
Volume152
Issue number1
DOIs
StatePublished - Jun 10 1999

All Science Journal Classification (ASJC) codes

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

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

  • Cite this