Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.jcss.2006.01.005
Title: Learning languages in a union
Authors: Jain, S. 
Ng, Y.K.
Tay, T.S. 
Keywords: Inductive inference
Unions of languages
Issue Date: 2007
Source: Jain, S., Ng, Y.K., Tay, T.S. (2007). Learning languages in a union. Journal of Computer and System Sciences 73 (1) : 89-108. ScholarBank@NUS Repository. https://doi.org/10.1016/j.jcss.2006.01.005
Abstract: In inductive inference, a machine is given words of a language (a recursively enumerable set in our setting) and the machine is said to identify the language if it correctly names the language. In this paper we study identifiability of classes of languages where the unions of up to a fixed number (n say) of languages from the class are provided as input. We distinguish between two different scenarios: in one scenario, the learner need only to name the language which results from the union; in the other, the learner must individually name the languages which make up the union (we say that the unioned language is discerningly identified). We define three kinds of identification criteria based on this and by the use of some classes of disjoint languages, demonstrate that the inferring power of each of these identification criterion decreases as we increase the number of languages allowed in the union, thus resulting in an infinite hierarchy for each identification criterion. That is, we show that for each n, there exists a class of disjoint languages where all unions of up to n languages from this class can be discerningly identified, but there is no learner which identifies every union of n + 1 languages from this class. A comparison between the different identification criteria also yielded similar hierarchies. We give sufficient conditions for classes of languages where the unions can be discerningly identified, and characterize such discerning learnability for the indexed families. We then give naturally occurring classes of languages that witness some of the earlier hierarchical results. Finally, we present language classes which are complete with respect to weak reduction (in terms of intrinsic complexity) for our identification criteria. © 2006 Elsevier Inc. All rights reserved.
Source Title: Journal of Computer and System Sciences
URI: http://scholarbank.nus.edu.sg/handle/10635/43104
ISSN: 00220000
DOI: 10.1016/j.jcss.2006.01.005
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

2
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

2
checked on Nov 21, 2017

Page view(s)

43
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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