nductive program synthesis addresses the problem of constructing recursive programs from incomplete specifications, typically input/output examples. Goal of this proposal is the advancement of classical (Summers like) approaches for example-driven, analytical synthesis of functional programs. In contrast to approaches of inductive logic programming and evolutionary computation, which are mainly search-based, analytical approaches have the advantage that synthesis effort is considerably lower.
However, current approaches typically are restricted to structural problems (such as reversing of a list) and rely on simple hypothesis languages (such as linear recursive program schemes). By reformulating the synthesis problem on the background of constructor-based term rewriting systems, taking into account modern techniques of functional programming, as well as moderate use of search-based (e. g. evolutionary) strategies and usage of background knowledge we hope to gain an approach whose efficiency is comparable to classical approaches but whose scope goes well beyond these approaches.
The proposed approach guarantees that the induced programs are a minimal generalization over examples and terminate. Besides applications to synthesis problems reported in literature, we plan to apply our approach in the domain of end-user programming support.