Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.ic.2017.05.002
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. https://doi.org/10.1016/j.ic.2017.05.002
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
URI: https://scholarbank.nus.edu.sg/handle/10635/177528
ISSN: 0890-5401
DOI: 10.1016/j.ic.2017.05.002
Appears in Collections:Staff Publications
Elements

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

OPEN

Post-printView/Download

Page view(s)

137
checked on May 12, 2022

Google ScholarTM

Check

Altmetric


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