Synthesis of Recursive Functions with Interdependent Parameters

We present a methodology for the inductive synthesis of recursive functions based upon the theoretical framework of context-free tree grammars. The synthesis task is splitted into two parts: First, a small set of positive input/output examples is transformed into a straight-forward ("initial") program by means of heuristic search; second, the straight-forward program is generalized to a recursive function. In this paper we concentrate on the second part of the synthesis task. That is, we deal with the problem of infering recurrence relations from straight-forward programs. We will describe our theoretical framework and propose an induction algorithm. Straight-forward programs are regarded as elements of some term algebra with unknown elements but with known rules for forming syntactically correct expressions. The synthesis task than is to fold such a term into a recursive program scheme (RPS). The algorithm works purely syntactically - without information about number and ordering of..