Page vii

11 Learning with Oracles 251 11.1 Introduction 251 11.2 Oracle scientists 251 11.3 Function identification by oracle scientists 252 11.4 Language identification by oracle scientists 257 11.5 Bibliographic notes 259 11.6 Exercises 259 12 Complexity Issues in Identification 261 12.1 Introduction 261 12.2 Mind change complexity 262 12.3 Number of examples required 264 12.4 An axiomatic approach to complexity of convergence 267 12.5 Strictly minimal identification of languages 268 12.6 Nearly minimal identification 273 12.7 Bibliographic notes 275 12.8 Exercises 277 13 Beyond Identification by Enumeration 281 13.1 Gold's and Barzdins' * conjectures 281 13.2 Fulk's refutation of Barzdins'* conjecture 282 13.3 Exercises 286 Bibliography 289 Notation Index 303 Author and Subject Index 309