Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.tcs.2018.12.022
Title: | Intrinsic complexity of partial learning | Authors: | JAIN, S KINBER, E |
Issue Date: | 12-Jul-2019 | Publisher: | Elsevier BV | Citation: | JAIN, S, KINBER, E (2019-07-12). Intrinsic complexity of partial learning. Theoretical Computer Science 776 : 43-63. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2018.12.022 | Abstract: | © 2018 Elsevier B.V. A partial learner in the limit [25], given a representation of the target language (a text), outputs a sequence of conjectures, where one correct conjecture appears infinitely many times and other conjectures each appear a finite number of times. Following [7] and [21], we define intrinsic complexity of partial learning, based on reducibilities between learning problems. Although the whole class of recursively enumerable languages is partially learnable (see [25]) and, thus, belongs to the complete learnability degree, we discovered a rich structure of incomplete degrees, reflecting different types of learning strategies (based, to some extent, on topological structures of the target language classes). We also exhibit examples of complete classes that illuminate the character of the strategies for partial learning of the hardest classes. | Source Title: | Theoretical Computer Science | URI: | https://scholarbank.nus.edu.sg/handle/10635/155272 | ISSN: | 0304-3975 | DOI: | 10.1016/j.tcs.2018.12.022 |
Appears in Collections: | Staff Publications Elements |
Show full item record
Files in This Item:
File | Description | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
partintrinfinal.pdf | 391.02 kB | Adobe PDF | OPEN | None | View/Download |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.