Page 276

		of mind changes based on the use of constructive ordinals to bound the number of mind changes. See Jain and Sharma [94] and Ambainis, Jain, and Sharma [4] for applications of this notion to the analysis of the complexity of learning natural classes of languages. More generalized notions of mind change complexity can be found in Ambainis, Freivalds, and Smith [3] and Sharma, Stephan, and Ventsov [174].

		The approach of bounding the number of examples before a scientist converges as a measure of complexity is due to Wiehagen [199, 198, 197]. These references also present a number of variants on this theme.

		The idea of total work performed by a scientist before the onset of convergence as a model of complexity is due to Daley and Smith [54]. Freivalds has [62] an alternative proposal in which the number of distinct hypotheses conjectured by a scientist is considered a measure for the complexity of identification.

		Freivalds [62] made the first attempt at an axiomatization of the complexity of identification for functions. The approach presented in this chapter is due to Daley and Smith [54]. Schäfer-Richter [167] has an alternative axiomatization.

		Restrictions on program size in the context of functions were first studied by Freivalds [61]. He also introduced the notions of nearly minimal identification and limiting standardizable with a recursive estimate. Chen [37] considered variants of nearly minimal identification for functions in the presence of anomalies in the final program. Kinber [107, 108] has a number of additional results on program-size restrictions for function identification.

		Case and Chi [27] adapted Freivalds' definition of nearly minimal function identification to languages. Jain and Sharma [89] considered strictly minimal identification, nearly minimal identification, and analogs of some of Kinber's notions for languages. Case, Jain, and Sharma [30] investigated nearly minimal identification in the context of vacillatory identification of languages.

		The subject of learning "fastest" hypotheses has not been as well investigated as that of learning succinct hypotheses. The interested reader is referred to Zeugmann [207].

		Recently, the idea of reduction from recursion theory has been employed to compare the difficulty of learning classes of concepts. This notion, referred to as intrinsic complexity, was first investigated by Freivalds, Kinber, and Smith [65] in the context of functions. Jain and Sharma [93] studied the intrinsic complexity of languages. See Jain and Sharma [95] for the structure of these reductions and Jain and Sharma [94] for connections between intrinsic complexity and mind change bounds measured by constructive ordinals.