Please use this identifier to cite or link to this item: https://doi.org/10.1137/070700577
Title: Mitotic classes in inductive inference
Authors: Jain, S. 
Stephan, F. 
Keywords: Inductive inference
Mitotic classes
Recursion theory
Reducibilities
Issue Date: 2008
Source: Jain, S., Stephan, F. (2008). Mitotic classes in inductive inference. SIAM Journal on Computing 38 (4) : 1283-1299. ScholarBank@NUS Repository. https://doi.org/10.1137/070700577
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. © 2008 Society for Industrial and Applied Mathematics.
Source Title: SIAM Journal on Computing
URI: http://scholarbank.nus.edu.sg/handle/10635/43066
ISSN: 00975397
DOI: 10.1137/070700577
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

1
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

1
checked on Nov 19, 2017

Page view(s)

32
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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