Characterization of a class of functions synthesized from examples by a summers like method using a B.M.W. matching technique
Jean-Pierre Jouannaud, Yves Kodratoff · International Joint Conference on Artificial Intelligence · 1979
This paper describes first a program synthesis from examples method using a SUMMERS like methodology together with a sophisticated pattern matching technique, the BOYER-MOORE-WEGBREIT algorithm. We then characterize the class of functions synthesized from a restricted BMW algorithm. Our methodology is founded on three grounds.The first one is a precise characterization of the list domains fitting the synthesis from examples problem. The second one is SUMMERS' technique of input-output examples transformation into computational traces. The third one is the description by a restricted program scheme of the functions in the class. It seems to us that the proofs methods easily extend to the general class.