Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/99214
Title: Characterizing language identification in terms of computable numberings
Authors: Jain, S. 
Sharma, A.
Issue Date: 6-Mar-1997
Citation: Jain, S.,Sharma, A. (1997-03-06). Characterizing language identification in terms of computable numberings. Annals of Pure and Applied Logic 84 (1) : 51-72. ScholarBank@NUS Repository.
Abstract: Identification of programs for computable functions from their graphs and identification of grammars (r. e. indices) for recursively enumerable languages from positive data are two extensively studied problems in the recursion theoretic framework of inductive inference. In the context of function identification, Freivalds et al. (1984) have shown that only those collections of functions, ℒ, are identifiable in the limit for which there exists a 1-1 computable numbering ψ and a discrimination function d such that (a) for each f ∈ ℒ, the number of indices i such that ψi = f is exactly one and (b) for each f ∈ ℒ, there are only finitely many indices i such that f and ψi, agree on the first d(i) arguments. A similar characterization for language identification in the limit has turned out to be difficult. A partial answer is provided in this paper. Several new techniques are introduced which have found use in other investigations on language identification.
Source Title: Annals of Pure and Applied Logic
URI: http://scholarbank.nus.edu.sg/handle/10635/99214
ISSN: 01680072
Appears in Collections:Staff Publications

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

Page view(s)

20
checked on Oct 5, 2018

Google ScholarTM

Check


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