### 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 language | English (US) |
---|---|

Pages (from-to) | 16-43 |

Number of pages | 28 |

Journal | Information and Computation |

Volume | 152 |

Issue number | 1 |

DOIs | |

State | Published - Jun 10 1999 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

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

### Cite this

*Information and Computation*,

*152*(1), 16-43. https://doi.org/10.1006/inco.1998.2782

}

*Information and Computation*, vol. 152, no. 1, pp. 16-43. https://doi.org/10.1006/inco.1998.2782

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

Research output: Contribution to journal › Article

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 -