Please use this identifier to cite or link to this item:
Title: Automatic learning from positive data and negative counterexamples
Authors: Jain S. 
Kinber E.
Stephan F. 
Keywords: Automatic classes
Automatic learning
Inductive inference
Iterative learning
Negative counterexamples
Issue Date: 2017
Publisher: Elsevier Inc.
Citation: Jain S., Kinber E., Stephan F. (2017). Automatic learning from positive data and negative counterexamples. Information and Computation 255 : 45-67. ScholarBank@NUS Repository.
Abstract: We introduce and study a model for learning in the limit by finite automata from positive data and negative counterexamples. The focus is on learning classes of languages with the membership problem computable by finite automata (so-called automatic classes). We show that, within the framework of our model, finite automata (automatic learners) can learn all automatic classes when memory of a learner is restricted by the size of the longest datum seen so far. We also study capabilities of automatic learners in our model with other restrictions on the memory and how the choice of negative counterexamples (arbitrary, or least, or the ones which are bounded by the largest positive datum seen so far) can impact automatic learnability. © 2017 Elsevier Inc.
Source Title: Information and Computation
ISSN: 0890-5401
DOI: 10.1016/j.ic.2017.05.002
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
automaticlearningpositivedata.pdf294.16 kBAdobe PDF



Google ScholarTM



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