Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Learning Languages in a Union

Sanjay JainContact Information, Yen Kaow NgContact Information and Tiong Seng TayContact Information

(6)  School of Computing, National University of Singapore, 119260, Singapore
(7)  School of Computing, National University of Singapore, 119260, Singapore
(8)  Department of Mathematics, National University of Singapore, 119260, Singapore
Abstract
In inductive inference,a machine is given words in a language and the machine is said to identify the language if it correctly names the language. In this paper we study classes of languages where the unions of up to a fixed number (n say) of languages from the class are identifiable. 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 naturally occurring classes of 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. A comparison between the different identification criteria also yielded similar hierarchies. 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. We give sufficient conditions for classes of languages where the unions can be discerningly identified. We also present language classes which are complete with respect to weak reduction (in terms of intrinsic complexity) for our identification criteria.

Contact Information Sanjay Jain
Email: sanjay@comp.nus.edu.sg

Contact Information Yen Kaow Ng
Email: ngyenkao@comp.nus.edu.sg

Contact Information Tiong Seng Tay
Email: mattayts@nus.edu.sg
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.108 • Server: MPWEB25
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)