Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/7008
Title: Language Learning without Overgeneralization
Authors: Kapur, Shyam
Bilardi, Gianfranco
Keywords: computer science
technical report
Issue Date: Nov-1990
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1168
Abstract: Language learnability is investigated in the Gold paradigm of inductive inference from positive data. Angluin gave a characterization of learnable families in this framework. Here, learnability of families of recursive languages is studied when the learner obeys certain natural constraints. Exactly learnable families are characterized for prudent learners with the following types of constraints: (0) conservative, (1) conservative and consistent, (2) conservative and responsive, and (3) conservative, consistent, and responsive. The class of learnable families is shown to strictly increase going from (3) to (2) and from (2) to (1), while it stays the same going from (1) to (0). It is also shown that, when exactness is not required, prudence, consistency and responsiveness, even together, do not restrict the power of conservative learners.
URI: http://hdl.handle.net/1813/7008
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
90-1168.pdf1.22 MBAdobe PDFView/Open
90-1168.ps318.05 kBPostscriptView/Open

Refworks Export

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

 

© 2014 Cornell University Library Contact Us