Name
Abstract | ||
|---|---|---|
For the natural notion of splitting classes into two disjoint subclasses via a recursive classifier working on texts, the question of how these splittings can look in the case of learnable classes is addressed. Here the strength of the classes is compared using the strong and weak reducibility from intrinsic complexity. It is shown that, for explanatorily learnable classes, the complete classes are also mitotic with respect to weak and strong reducibility, respectively. But there is a weakly complete class that cannot be split into two classes which are of the same complexity with respect to strong reducibility. It is shown that, for complete classes for behaviorally correct learning, one-half of each splitting is complete for this learning notion as well. Furthermore, it is shown that explanatorily learnable and recursively enumerable classes always have a splitting into two incomparable classes; this gives an inductive inference counterpart of the Sacks splitting theorem from recursion theory. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/070700577 | SIAM J. Comput. |
Keywords | Field | DocType |
learnable class,explanatorily learnable class,strong reducibility,weak reducibility,explanatorily learnable,splitting class,sacks splitting theorem,weakly complete class,complete class,behaviorally correct learning,inductive inference,mitotic classes,recursion theory,reducibilities | Inductive reasoning,Discrete mathematics,Combinatorics,Disjoint sets,Splitting theorem,Computability theory,Recursively enumerable language,Reduction (recursion theory),Classifier (linguistics),Mathematics,Recursion | Journal |
Volume | Issue | ISSN |
38 | 4 | 0097-5397 |
Citations | PageRank | References |
1 | 0.38 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sanjay Jain | 1 | 1647 | 177.87 |
| Frank Stephan | 2 | 313 | 28.88 |