Inductive Synthesis of Recursive Functional Programs

March 23, 2011
Emanuel Kitzelmann | University of California

Inductive program synthesis (IPS) is concerned with the automated construction of computer programs from incomplete specifications, such as input-output examples. Application fields are, e.g., end-user programming, algorithm development, and intelligent agents that autonomously acquire productive problem-solving knowledge. This talk focuses on the inductive synthesis of recursive functional programs. I introduce the recent IPS algorithm IGOR2 that combines analytical methods with search in program spaces in order to achieve a sensible trade-off between expressivity and efficiency. Experiments with typical list-processing functions and with benchmark-problems from problem-solving and automated planning show promising results.

Speaker Details

Emanuel Kitzelmann is a postdoctoral research fellow and member of the Artificial Intelligence (AI) Group at the International Computer Science Institute (ICSI) in Berkeley. He received his MS and PhD (with summa cum laude) in Computer Science from Technical University of Berlin and University of Bamberg, Germany, respectively.

His research interests are on AI and inductive program synthesis. For his PhD thesis, he developed a competitive algorithm for the synthesis of recursive functional programs from examples that combines analysis of examples with search in program spaces. He currently applies that algorithm to learning hierarchical, recursive domain knowledge for planning and problem-solving. Emanuel published several articles in peer-reviewed journals, conferences and workshops. He co-organized the Workshop on Approaches and Applications of Inductive Programming and maintains the website inductive-programming.org. He was PC chair of the Conference on Artificial General Intelligence and reviewed for several AI and program synthesis conferences and workshops.