Closedness properties in ex-identification*

Authors: Kalvis Apsitis, Rusins Freivalds, Raimonds Simanovskis and Juris Smotrovs

Source: Theoretical Computer Science Vol. 268, Issue 2, 17 October 2001, pp. 367 - 393.

Abstract. In this paper we investigate in which cases unions of identifiable classes are also necessarily identifiable. We consider identification in the limit with bounds on mindchanges and anomalies. Though not closed under the set union, these identification types still have features resembling closedness. For each of them we find n such that

(1) if every union of n - 1 classes out of U1, ... , Un is identifiable, so is the union of all n classes;
(2) there are classes U1, ... , Un - 1 such that every union of n - 2 classes out of them is identifiable, while the union of n - 1 classes is not.

We show that by finding these n we can distinguish which requirements put on the identifiability of unions of classes are satisfiable and which are not. We also show how our problem is connected with team learning.

* Supported by Latvia Science Council Grant 96.0282.

©Copyright 2001 Elsevier Science B.V.