Page 219

		§9.7 Bibliographic Notes

		Team identification of functions () was first defined by Case, motivated by the nonunion theorem of Blum and Blum [18]. It was studied extensively by Smith [178]. The general case of team identification (m out of n) is due to Osherson, Stob, and Weinstein [139]. Probabilistic scientists in the context of learning were first considered by Freivalds [60]. Pitt [149] was the first to notice the connection between team identification and probabilistic identification of functions.

		Jain and Sharma [92] investigated team identification of languages. Proposition 9.36 also appears in Osherson, Stob, and Weinstein [139], and may also be shown using an argument from Pitt [149] about probabilistic language learning.

		Recently there has been lively interest in the interaction between probability, teams, and the number of allowable mind changes (see Wiehagen, Freivalds, and Kinber [201] and Daley and Kalyanasundaram [48]). Considerable work has been devoted to the special case of 0 mind changes (i.e., finite identification). We direct the reader to Freivalds [63], Jain, Sharma, and Velauthapillai [97], Daley, Pitt, Velauthapillai, and Will [53], Daley, Kalyanasundaram, and Velauthapillai [50]. The problem of teams for Popperian finite identification of functions is addressed by Daley, Kalyanasundaram, and Velauthapillai [51] and Daley and Kalyanasundaram [49].

		Allowing teams of finite learners to make up to a finite number of errors in the conjectured hypothesis has been addressed by Daley, Kalyanasundaram, and Velauthapillai[52]. Behaviorally correct function identification by teams has been studied by Daley [46, 47]. In the context of language identification, work has hardly begun on other criteria. We direct the reader to Jain and Sharma [90] for results on finite, vacillatory, and behaviorally correct identification of languages by teams. Meyer [130] has investigated probabilistic identification of indexed families of computable languages (see Meyer [131] for interaction between monotonicity constraints and probabilistic identification of indexed families of computable languages).

		An attempt at investigating some general properties of teams has been made by Ambainis [2]. The notion of asymmetric teams has been introduced and studied by Apsitis *, Freivalds, and Smith [7].

		§9.8 Exercises

		9-1 This exercise investigates whether, in the context of functions, anomalies in the final program can be traded for extra team members. Show: For all i, and , ,where .