The Synthesis of Language Learners

Ganesh R. Baliga, John Case, Sanjay Jain

Research output: Contribution to journalArticle

28 Citations (Scopus)

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

Fingerprint

Synthesis
Learnability
Subset
Decision Procedures
Grammar
Language
Family
Corollary
Class
Lower bound

All Science Journal Classification (ASJC) codes

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

Cite this

Baliga, Ganesh R. ; Case, John ; Jain, Sanjay. / The Synthesis of Language Learners. In: Information and Computation. 1999 ; Vol. 152, No. 1. pp. 16-43.
@article{bcc1654cef014c4f846be66ade52317b,
title = "The Synthesis of Language Learners",
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).",
author = "Baliga, {Ganesh R.} and John Case and Sanjay Jain",
year = "1999",
month = "6",
day = "10",
doi = "10.1006/inco.1998.2782",
language = "English (US)",
volume = "152",
pages = "16--43",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Elsevier Inc.",
number = "1",

}

The Synthesis of Language Learners. / Baliga, Ganesh R.; Case, John; Jain, Sanjay.

In: Information and Computation, Vol. 152, No. 1, 10.06.1999, p. 16-43.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The Synthesis of Language Learners

AU - Baliga, Ganesh R.

AU - Case, John

AU - Jain, Sanjay

PY - 1999/6/10

Y1 - 1999/6/10

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=0345867476&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0345867476&partnerID=8YFLogxK

U2 - 10.1006/inco.1998.2782

DO - 10.1006/inco.1998.2782

M3 - Article

AN - SCOPUS:0345867476

VL - 152

SP - 16

EP - 43

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - 1

ER -