Please use this identifier to cite or link to this item:
https://doi.org/10.1007/978-3-642-29952-0_41
DC Field | Value | |
---|---|---|
dc.title | On the amount of nonconstructivity in learning formal languages from positive data | |
dc.contributor.author | Jain, S. | |
dc.contributor.author | Stephan, F. | |
dc.contributor.author | Zeugmann, T. | |
dc.date.accessioned | 2013-07-23T09:29:04Z | |
dc.date.available | 2013-07-23T09:29:04Z | |
dc.date.issued | 2012 | |
dc.identifier.citation | Jain, S.,Stephan, F.,Zeugmann, T. (2012). On the amount of nonconstructivity in learning formal languages from positive data. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7287 LNCS : 423-434. ScholarBank@NUS Repository. <a href="https://doi.org/10.1007/978-3-642-29952-0_41" target="_blank">https://doi.org/10.1007/978-3-642-29952-0_41</a> | |
dc.identifier.isbn | 9783642299513 | |
dc.identifier.issn | 03029743 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/43252 | |
dc.description.abstract | Nonconstructive computations by various types of machines and automata have been considered by e.g., Karp and Lipton [18] and Freivalds [9, 10]. They allow to regard more complicated algorithms from the viewpoint of more primitive computational devices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices with respect to solving a specific problem. This paper studies the amount of nonconstructivity needed to learn classes of formal languages from positive data. Different learning types are compared with respect to the amount of nonconstructivity needed to learn indexable classes and recursively enumerable classes, respectively, of formal languages from positive data. Matching upper and lower bounds for the amount of nonconstructivity needed are shown. © 2012 Springer-Verlag. | |
dc.description.uri | http://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1007/978-3-642-29952-0_41 | |
dc.source | Scopus | |
dc.type | Conference Paper | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.contributor.department | MATHEMATICS | |
dc.description.doi | 10.1007/978-3-642-29952-0_41 | |
dc.description.sourcetitle | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | |
dc.description.volume | 7287 LNCS | |
dc.description.page | 423-434 | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Staff Publications |
Show simple 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.