Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/99323
Title: Kolmogorov numberings and minimal identification
Authors: Freivalds, R.
Jain, S. 
Issue Date: 30-Nov-1997
Source: Freivalds, R.,Jain, S. (1997-11-30). Kolmogorov numberings and minimal identification. Theoretical Computer Science 188 (1-2) : 175-194. ScholarBank@NUS Repository.
Abstract: Identification of programs for computable functions from their graphs by algorithmic devices is a well studied problem in learning theory. Freivalds and Chen consider identification of 'minimal' and 'nearly minimal' programs for functions from their graphs. To address certain problems in minimal identification for Gödel numberings, Freivalds later considered minimal identification in Kolmogorov numberings. Kolmogorov numberings are in some sense optimal numberings and have some nice properties. We prove certain separation results for minimal identification in every Kolmogorov numbering. In addition we also compare minimal identification in Gödel numberings versus minimal identification in Kolmogorov numberings.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/99323
ISSN: 03043975
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

17
checked on Mar 8, 2018

Google ScholarTM

Check


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