查看文章

This paper is concerned with model inference problems and algorithms. A model inference problem is an abstraction of the problem faced by a scientist, working in some domain under some fixed conceptual framework, performing experiments and trying to find a theory capable of explaining their results. In this abstraction the domain of inquiry is the domain of some unknown model M for a given first order language L, experiments are tests of the truth of sentences of L in M, and the goal is to find a set of true hypotheses that imply all true testable sentences.

The main result of this paper is a general, incremental algorithm for solving model inference problems, which is based on the Popperian methodology of conjectures and refutations [Popper 59, Popper 68]. The algorithm can be shown to identify in the limit [Gold 67] any model in a family of complexity classes of models, it is the most powerful of its kind, and is …