Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2007.08.010
Title: Learning languages from positive data and a limited number of short counterexamples
Authors: Jain, S. 
Kinber, E.
Keywords: Counterexamples
Inductive inference
Learning in the limit
Positive data
Issue Date: 2007
Citation: Jain, S., Kinber, E. (2007). Learning languages from positive data and a limited number of short counterexamples. Theoretical Computer Science 389 (1-2) : 190-218. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2007.08.010
Abstract: We consider two variants of a model for learning languages in the limit from positive data and a limited number of short negative counterexamples (counterexamples are considered to be short if they are smaller than the largest element of input seen so far). Negative counterexamples to a conjecture are examples which belong to the conjectured language but do not belong to the input language. Within this framework, we explore how/when learners using n short (arbitrary) negative counterexamples can be simulated (or simulate) using least short counterexamples or just 'no' answers from a teacher. We also study how a limited number of short counterexamples fairs against unconstrained counterexamples, and also compare their capabilities with the data that can be obtained from subset, superset, and equivalence queries (possibly with counterexamples). A surprising result is that just one short counterexample can sometimes be more useful than any bounded number of counterexamples of arbitrary sizes. Most of the results exhibit salient examples of languages learnable or not learnable within corresponding variants of our models. © 2007 Elsevier Ltd. All rights reserved.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/39436
ISSN: 03043975
DOI: 10.1016/j.tcs.2007.08.010
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

1
checked on Jul 10, 2018

WEB OF SCIENCETM
Citations

1
checked on Jun 27, 2018

Page view(s)

50
checked on Jun 8, 2018

Google ScholarTM

Check

Altmetric


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