Page 108

		5.45 Definition

		(a) .

		(b) .

		A conservative scientist thus never abandons a locally successful conjecture, that is, a conjecture that generates all the data seen to date. It is easy to verify that the collection of all finite languages and the collection. of all co-singleton languages can be identified by conservative scientists.

		The following proposition implies that conservatism is restrictive.

		5.46 Proposition (Angluin [6]) .

		Proof: This argument is essentially the same as that for Proposition 5.25. Consider the class defined in that proof and suppose that Mj is a conservative scientist that identifies . As argued in the proof of Proposition 5.25, Mj must identify the text , for Lj. Thus there is a least pair such that Mj(T[n]) = i and . So is not identified by Mj, since on the text Mjmust continue to output i by the conservativeness of Mj.

		It turns out that both global and class versions of conservatism render the same collections of languages identifiable, as implied by the next proposition. Its proof is discussed in Exercise 5-21.

		5.47 Proposition [TxtEx]conservative = [TxtEx]clss-conservative.

		§5.5.2 Generalization Strategies

		We now consider a collection of strategies that require scientists to "improve" upon their successive conjectures. A scientist can begin by hypothesizing an index for a language smaller than the target language and then build to the target language. Such strategies are referred to as generalization strategies, and they model bottom-up or specific-to-general searches in artificial systems for empirical inquiry. For example, see systems such as Muggleton and Feng's Golem [134].

		Three different generalization strategies have been proposed.

		5.48 Definition (Jantke [99])