Representative sample of LISP program inference from examples
Nobuhiro Inuzuka, Keníchi Takahashi, Naohiro Ishii · International Journal of Systems Science · 1992
The inference of LISP programs from their input-output behaviour is one of the most significant subjects in the study of inductive inference. P.D. Summers gave the inference algorithm for this problem. His method uses a recurrence relation among multiple examples. We have extended this method. By characterizing the set of examples, we introduce the notion of a representative sample that describes the capability of the LISP program appropriately. That is, a representative sample is the set of examples that are the simplest ones of all the examples that behave in the same way. Then, we give a condition that assures the existence of a representative sample and partial correctness of the inference algorithm. Furthermore, we propose an interactive procedure that transforms an arbitrary given set of examples into the representative one. This procedure makes the inference algorithm flexible.