On a question of nearly minimal identification of functions

Please use this identifier to cite or link to this item: https://doi.org/10.1016/S0020-0190(99)00051-4

Title:	On a question of nearly minimal identification of functions
Authors:	Jain, S.
Issue Date:	1999
Citation:	Jain, S. (1999). On a question of nearly minimal identification of functions. Information Processing Letters 70 (3) : 113-117. ScholarBank@NUS Repository. https://doi.org/10.1016/S0020-0190(99)00051-4
Abstract:	Suppose A and B are classes of recursive functions. A is said to be an m-cover (-cover) for B, iff for each g∈B, there exists an f∈A such that f differs from g on at most m inputs (finitely many inputs). C, a class of recursive functions, is a-immune iff C is infinite and every recursively enumerable subclass of C has a finite a-cover. C is a-isolated iff C is finite or a-immune. Chen (1981) conjectured that every class of recursive functions that is MEx m-identifiable is *-isolated. We refute this conjecture.
Source Title:	Information Processing Letters
URI:	http://scholarbank.nus.edu.sg/handle/10635/39419
ISSN:	00200190
DOI:	10.1016/S0020-0190(99)00051-4
Appears in Collections:	Staff Publications

There are no files associated with this item.

Check