Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/111197
Title: On the non-existence of maximal inference degrees for language identification
Authors: Jain, S. 
Sharma, A.
Keywords: inductive inference
Machine learning
methodology of science
recursion theory
theory of computation
Issue Date: 20-Aug-1993
Source: Jain, S.,Sharma, A. (1993-08-20). On the non-existence of maximal inference degrees for language identification. Information Processing Letters 47 (2) : 81-88. ScholarBank@NUS Repository.
Abstract: Identification of grammars (r.e. indices) for recursively enumerable languages from positive data by algorithmic devices is a well-studied problem in learning theory. The present paper considers identification of r.e. languages by machines that have access to membership oracles for noncomputable sets. It is shown that for any set A there exists another set B such that the collections of r.e. languages that can be identified by machines with access to a membership oracle for B is strictly larger than the collections of r.e. languages that can be identified by machines with access to a membership oracle for A. In other words, there is no maximal inference degree for language identification. © 1993.
Source Title: Information Processing Letters
URI: http://scholarbank.nus.edu.sg/handle/10635/111197
ISSN: 00200190
Appears in Collections:Staff Publications

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

Page view(s)

25
checked on Jan 19, 2018

Google ScholarTM

Check


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