Please use this identifier to cite or link to this item:
|Automatic learning from positive data and negative counterexamples
|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
|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.
|Information and Computation
|Appears in Collections:
Show full item record
Files in This Item:
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.