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.
|
 |
Learning in Friedberg Numberings
| |
|
Learning in Friedberg Numberings
Sanjay Jain4 and Frank Stephan5 
| (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.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|