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 in Friedberg Numberings

Sanjay JainContact Information and Frank StephanContact Information

(4)  Department of Computer Science, National University of Singapore, Singapore 117590, Republic of Singapore
(5)  Department of Computer Science and Department of Mathematics, National University of Singapore, Singapore 117543, Republic of Singapore
Abstract
In this paper we consider learnability in some special numberings, such as Friedberg numberings, which contain all the recursively enumerable languages, but have simpler grammar equivalence problem compared to acceptable numberings. We show that every explanatorily learnable class can be learnt in some Friedberg numbering. However, such a result does not hold for behaviourally correct learning or finite learning. One can also show that some Friedberg numberings are so restrictive that all classes which can be explanatorily learnt in such Friedberg numberings have only finitely many infinite languages. We also study similar questions for several properties of learners such as consistency, conservativeness, prudence, iterativeness and non U-shaped learning. Besides Friedberg numberings, we also consider the above problems for programming systems with K-recursive grammar equivalence problem.

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

Contact Information Frank Stephan
Email: fstephan@comp.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.112 • Server: mpweb08
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)