Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39102
Title: The Synthesis of Language Learners
Authors: Baliga, G.R.
Case, J.
Jain, S. 
Issue Date: 1999
Source: Baliga, G.R.,Case, J.,Jain, S. (1999). The Synthesis of Language Learners. Information and Computation 152 (1) : 16-43. ScholarBank@NUS Repository.
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). © 1999 Academic Press.
Source Title: Information and Computation
URI: http://scholarbank.nus.edu.sg/handle/10635/39102
ISSN: 08905401
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

42
checked on Dec 8, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.