返回Google圖書搜尋

Synthesis of Recursive Programs from Finite Examples by Detection of Macro-functions

出版	Leiter der Fachbibliothek Informatik, Sekretariat FR 5-4, 2001
URL	http://books.google.com.hk/books?id=QwQUuAAACAAJ&hl=&source=gbs_api

註釋Abstract: "The paper is concerned with a special problem of inductive synthesis of recursive functional programs. Starting point for induction is a complete set of example computations in a finite domain. The example computations are mainly obtained by a problem solver in form of an initial shortest path tree spanning the problem graph. It is shown that the initial tree can be automatically transformed into a finite initial program. Induction (generalization-to-n) results in a program which transforms each initial state of any problem domain which is a recursive extension of the given finite domain into the desired output. Programs are represented in an abstract way by terms, i.e., elements of a term algebra. Thus, our approach is simultaneously an example of the design of recursive algorithms from finite cases. The core of our investigations is to detect sub-structures in the finite initial trees playing the role of 'macro-functions' (sub-routines). As compared to the 'macro-operators' used in planning the main point of our approach is the definition of macros containing all cases (operation sequences) reaching the corresponding goal including the trivial one that the goal is already true in a state. A special case of macro-induction is the invention of complex (recursive) predicates. We show that in some cases induction can only be performed after the introduction of the detected macro-functions, considering them as elementary functions in a new, extended term algebra. In the special cases considered in this paper, the programs which can be induced after the introduction of macro-functions are linear or linear recursive, i.e. have a macro-structure which cannot easily be seen in the set (tree) of initial example computations. At the end of the paper, cognitive aspects -- especially connections to creative thinking -- are discussed."