Please use this identifier to cite or link to this item:
https://doi.org/10.1007/978-3-642-28332-1_22
Title: | Learnability of co-r.e. classes | Authors: | Gao, Z. Stephan, F. |
Issue Date: | 2012 | Citation: | Gao, Z.,Stephan, F. (2012). Learnability of co-r.e. classes. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7183 LNCS : 252-263. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-28332-1_22 | Abstract: | The object of investigation in this paper is the learnability of co-recursively enumerable (co-r.e.) languages based on Gold's [11] original model of inductive inference. In particular, the following learning models are studied: finite learning, explanatory learning, vacillatory learning and behaviourally correct learning. The relative effects of imposing further learning constraints, such as conservativeness and prudence on these various learning models are also investigated. Moreover, an extension of Angluin's [1] characterisation of identifiable indexed families of recursive languages to families of conservatively learnable co-r.e. classes is presented. In this connection, the paper considers the learnability of indexed families of recursive languages, uniformly co-r.e. classes as well as other general classes of co-r.e. languages. A containment hierarchy of co-r.e. learning models is thereby established; while this hierarchy is quite similar to its r.e. analogue, there are some surprising collapses when using a co-r.e. hypothesis space; for example vacillatory learning collapses to explanatory learning. © 2012 Springer-Verlag. | Source Title: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | URI: | http://scholarbank.nus.edu.sg/handle/10635/104582 | ISBN: | 9783642283314 | ISSN: | 03029743 | DOI: | 10.1007/978-3-642-28332-1_22 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.